Cấu trúc dữ liệu và thuật toán -CHƯƠNG II CẤU TRÚC DỮ LIỆU-CÁC LOẠI HÀNG ĐỢI

Cấu trúc dữ liệu và thuật toán -CHƯƠNG II CẤU TRÚC DỮ LIỆU-CÁC LOẠI HÀNG ĐỢI

2.3. Các loại hàng đợi

Hàng đợi là một cấu trúc dữ liệu hữu ích trong lập trình. Nó tương tự như hàng đợi mua vé bên ngoài rạp chiếu phim, nơi người đầu tiên vào hàng đợi là người đầu tiên nhận được vé.

Có bốn loại hàng đợi khác nhau:

1. Hàng đợi đơn giản
2. Hàng đợi vòng tròn
3. Hàng đợi ưu tiên
4. Hàng đợi kết thúc kép

2.3.1.Hàng đợi đơn giản

Trong hàng đợi đơn giản, việc thêm vào diễn ra ở phía sau và việc xóa diễn ra ở phía trước. Nó tuân thủ nghiêm ngặt quy tắc FIFO (vào trước ra trước).

Simple Queue Representation

2.3.2.Hàng đợi tròn

Trong hàng đợi tròn, phần tử cuối cùng trỏ tới phần tử đầu tiên tạo thành liên kết tròn.

Biểu diễn hàng đợi tròn

Ưu điểm chính của hàng đợi vòng tròn so với hàng đợi đơn giản là sử dụng bộ nhớ tốt hơn. Nếu vị trí cuối cùng đầy và vị trí đầu tiên trống, chúng ta có thể chèn một phần tử vào vị trí đầu tiên. Hành động này không thể thực hiện được trong hàng đợi đơn giản.

2.3.3.Hàng đợi ưu tiên

Hàng đợi ưu tiên là một loại hàng đợi đặc biệt trong đó mỗi phần tử được liên kết với một mức độ ưu tiên và được phục vụ theo mức độ ưu tiên của nó. Nếu các phần tử có cùng mức độ ưu tiên xuất hiện, chúng được phục vụ theo thứ tự của chúng trong hàng đợi.

Biểu diễn hàng đợi ưu tiên

Việc chèn diễn ra dựa trên sự xuất hiện của các giá trị và việc xóa diễn ra dựa trên mức độ ưu tiên.

2.3.4.Deque (Hàng đợi hai đầu)

Trong hàng đợi hai đầu, việc chèn và xóa các phần tử có thể được thực hiện từ phía trước hoặc phía sau. Do đó, nó không tuân theo quy tắc FIFO (First In First Out).

Biểu diễn hàng đợi hai đầu

2.4.Cấu trúc dữ liệu hàng đợi tròn

Hàng đợi hình tròn là phiên bản mở rộng của hàng đợi thông thường, trong đó phần tử cuối cùng được kết nối với phần tử đầu tiên. Do đó tạo thành cấu trúc giống hình tròn.

Biểu diễn hàng đợi tròn

Hàng đợi tròn giải quyết được hạn chế lớn của hàng đợi thông thường. Trong hàng đợi thông thường, sau một chút chèn và xóa, sẽ có không gian trống không sử dụng được.

Giới hạn của hàng đợi thông thường

Ở đây, chỉ có thể sử dụng chỉ mục 0 và 1 sau khi đặt lại hàng đợi (xóa tất cả các phần tử). Điều này làm giảm kích thước thực tế của hàng đợi.

2.4.1.Hàng đợi tròn hoạt động như thế nào

Hàng đợi tròn hoạt động theo quy trình tăng dần theo vòng tròn, tức là khi chúng ta cố gắng tăng con trỏ và chúng ta đạt đến cuối hàng đợi, chúng ta bắt đầu từ đầu hàng đợi.

Ở đây, việc tăng dần theo vòng tròn được thực hiện bằng cách chia modulo với kích thước hàng đợi. Nghĩa là,

Nếu REAR + 1 == 5 (tràn!), REAR = (REAR + 1)%5 = 0 (bắt đầu hàng đợi)

2.4.2.Hoạt động hàng đợi tuần hoàn

Hàng đợi vòng tròn hoạt động như sau:

1. hai con trỏ FRONT và REAR
2. FRONT theo dõi phần tử đầu tiên của hàng đợi
3. REAR theo dõi phần tử cuối cùng của hàng đợi
4. ban đầu, đặt giá trị của FRONT và REAR thành -1

1. Hoạt động Enqueue

1. kiểm tra xem hàng đợi đã đầy chưa
2. đối với phần tử đầu tiên, đặt giá trị của FRONT thành 0
3. tăng tuần hoàn chỉ số REAR lên 1 (tức là nếu phần tử phía sau đạt đến cuối, phần tử tiếp theo sẽ ở đầu hàng đợi)
4. thêm phần tử mới vào vị trí được trỏ tới bởi REAR

2. Hoạt động Dequeue

1. kiểm tra xem hàng đợi có trống không
2. trả về giá trị được trỏ bởi FRONT
3. tăng tuần hoàn chỉ số FRONT lên 1
4. đối với phần tử cuối cùng, đặt lại giá trị của FRONT và REAR thành -1

Tuy nhiên, kiểm tra hàng đợi đầy có một trường hợp bổ sung mới:

Trường hợp 1: FRONT = 0 && REAR == SIZE - 1

Trường hợp 2: FRONT = REAR + 1

Trường hợp thứ hai xảy ra khi REAR bắt đầu từ 0 do tăng dần theo vòng tròn và khi giá trị của nó chỉ nhỏ hơn FRONT 1, hàng đợi đã đầy.

Các hoạt động Enqueue và Dequeue

2.4.3.Triển khai hàng đợi tuần hoàn trong Python, Java, C và C++

Cách triển khai hàng đợi phổ biến nhất là sử dụng mảng, nhưng cũng có thể triển khai bằng danh sách.

#Python

# Circular Queue implementation in Python

class MyCircularQueue():

    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.head = self.tail = -1

    # Insert an element into the circular queue
    def enqueue(self, data):

        if ((self.tail + 1) % self.k == self.head):
            print("The circular queue is full\n")

        elif (self.head == -1):
            self.head = 0
            self.tail = 0
            self.queue[self.tail] = data
        else:
            self.tail = (self.tail + 1) % self.k
            self.queue[self.tail] = data

    # Delete an element from the circular queue
    def dequeue(self):
        if (self.head == -1):
            print("The circular queue is empty\n")

        elif (self.head == self.tail):
            temp = self.queue[self.head]
            self.head = -1
            self.tail = -1
            return temp
        else:
            temp = self.queue[self.head]
            self.head = (self.head + 1) % self.k
            return temp

    def printCQueue(self):
        if(self.head == -1):
            print("No element in the circular queue")

        elif (self.tail >= self.head):
            for i in range(self.head, self.tail + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.head, self.k):
                print(self.queue[i], end=" ")
            for i in range(0, self.tail + 1):
                print(self.queue[i], end=" ")
            print()

# Your MyCircularQueue object will be instantiated and called as such:
obj = MyCircularQueue(5)
obj.enqueue(1)
obj.enqueue(2)
obj.enqueue(3)
obj.enqueue(4)
obj.enqueue(5)
print("Initial queue")
obj.printCQueue()

obj.dequeue()
print("After removing an element from the queue")
obj.printCQueue()

#Java

// Circular Queue implementation in Java
public class CQueue {
  int SIZE = 5; // Size of Circular Queue
  int front, rear;
  int items[] = new int[SIZE];

  CQueue() {
    front = -1;
    rear = -1;
  }

  // Check if the queue is full
  boolean isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    if (front == rear + 1) {
      return true;
    }
    return false;
  }

  // Check if the queue is empty
  boolean isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  // Adding an element
  void enQueue(int element) {
    if (isFull()) {
      System.out.println("Queue is full");
    } else {
      if (front == -1)
        front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      System.out.println("Inserted " + element);
    }
  }

  // Removing an element
  int deQueue() {
    int element;
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return (-1);
    } else {
      element = items[front];
      if (front == rear) {
        front = -1;
        rear = -1;
      } /* Q has only one element, so we reset the queue after deleting it. */
      else {
        front = (front + 1) % SIZE;
      }
      return (element);
    }
  }

  void display() {
    /* Function to display status of Circular Queue */
    int i;
    if (isEmpty()) {
      System.out.println("Empty Queue");
    } else {
      System.out.println("Front -> " + front);
      System.out.println("Items -> ");
      for (i = front; i != rear; i = (i + 1) % SIZE)
        System.out.print(items[i] + " ");
      System.out.println(items[i]);
      System.out.println("Rear -> " + rear);
    }
  }

  public static void main(String[] args) {

    CQueue q = new CQueue();

    // Fails because front = -1
    q.deQueue();

    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    // Fails to enqueue because front == 0 && rear == SIZE - 1
    q.enQueue(6);

    q.display();

    int elem = q.deQueue();

    if (elem != -1) {
      System.out.println("Deleted Element is " + elem);
    }
    q.display();

    q.enQueue(7);

    q.display();

    // Fails to enqueue because front == rear + 1
    q.enQueue(8);
  }

}
 

#C

// Circular Queue implementation in C

#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = -1, rear = -1;

// check if the queue is full
int isFull() {
  if ((front == (rear + 1) % SIZE) || (front == 0 && rear == SIZE - 1)) return 1;
  return 0;
}

// check if the queue is empty
int isEmpty() {
  if (front == -1) return 1;
  return 0;
}

// adding an element
void enQueue(int element) {
  if (isFull())
    printf("\n Queue is full!! \n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    items[rear] = element;
    printf("\n Inserted -> %d", element);
  }
}

// removing an element
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\n Queue is empty !! \n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } 
    // Q has only one element, so we reset the 
    // queue after dequeing it. ?
    else {
      front = (front + 1) % SIZE;
    }
    printf("\n Deleted element -> %d \n", element);
    return (element);
  }
}

// display the queue
void display() {
  int i;
  if (isEmpty())
    printf(" \n Empty Queue\n");
  else {
    printf("\n Front -> %d ", front);
    printf("\n Items -> ");
    for (i = front; i != rear; i = (i + 1) % SIZE) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("\n Rear -> %d \n", rear);
  }
}

int main() {
  // fails because front = -1
  deQueue();

  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  // fails to enqueue because front == 0 && rear == SIZE - 1
  enQueue(6);

  display();
  deQueue();

  display();

  enQueue(7);
  display();

  // fails to enqueue because front == rear + 1
  enQueue(8);

  return 0;
}
 

#C++

// Circular Queue implementation in C++

#include <iostream>
#define SIZE 5 /* Size of Circular Queue */

using namespace std;

class Queue {
   private:
  int items[SIZE], front, rear;

   public:
  Queue() {
    front = -1;
    rear = -1;
  }
  // Check if the queue is full
  bool isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    if (front == (rear + 1) % SIZE) {
      return true;
    }
    return false;
  }

  // Check if the queue is empty
  bool isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }
  // Adding an element
  void enQueue(int element) {
    if (isFull()) {
      cout << "Queue is full" << endl;
    } else {
      if (front == -1) front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      cout << endl
         << "Inserted " << element << endl;
    }
  }
  // Removing an element
  int deQueue() {
    int element;
    if (isEmpty()) {
      cout << "Queue is empty" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front == rear) {
        front = -1;
        rear = -1;
      }
      // Q has only one element,
      // so we reset the queue after deleting it.
      else {
        front = (front + 1) % SIZE;
      }
      return (element);
    }
  }

  void display() {
    // Function to display status of Circular Queue
    int i;
    if (isEmpty()) {
      cout << endl
         << "Empty Queue" << endl;
    } else {
      cout << "Front -> " << front;
      cout << endl
         << "Items -> ";
      for (i = front; i != rear; i = (i + 1) % SIZE)
        cout << items[i] << "\t";
      cout << items[i];
      cout << endl
         << "Rear -> " << rear << endl;
    }
  }
};

int main() {
  Queue q;

  // Fails because front = -1
  q.deQueue();

  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);

  // Fails to enqueue because front == 0 && rear == SIZE - 1
  q.enQueue(6);

  q.display();

  int elem = q.deQueue();

  if (elem != -1)
    cout << endl
       << "Deleted Element is " << elem << endl;

  q.display();

  q.enQueue(7);

  q.display();

  // Fails to enqueue because front == rear + 1
  q.enQueue(8);

  return 0;
}
 

2.4.4.Phân tích độ phức tạp của hàng đợi tuần hoàn

Độ phức tạp của các hoạt động enqueue và dequeue của hàng đợi tuần hoàn là O(1) đối với (các triển khai mảng).

2.4.5.Ứng dụng của Hàng đợi vòng tròn

1. Lập lịch CPU
2. Quản lý bộ nhớ
3. Quản lý lưu lượng

2.5. Hàng đợi ưu tiên

Hàng đợi ưu tiên là một loại hàng đợi đặc biệt trong đó mỗi phần tử được liên kết với một giá trị ưu tiên. Và, các phần tử được phục vụ dựa trên mức độ ưu tiên của chúng. Nghĩa là, các phần tử có mức độ ưu tiên cao hơn sẽ được phục vụ trước.

Tuy nhiên, nếu các phần tử có cùng mức độ ưu tiên xuất hiện, chúng sẽ được phục vụ theo thứ tự của chúng trong hàng đợi.

Gán giá trị ưu tiên

Thông thường, giá trị của chính phần tử được xem xét để gán mức độ ưu tiên. Ví dụ,

Phần tử có giá trị cao nhất được coi là phần tử có mức độ ưu tiên cao nhất. Tuy nhiên, trong các trường hợp khác, chúng ta có thể coi phần tử có giá trị thấp nhất là phần tử có mức độ ưu tiên cao nhất.

Chúng ta cũng có thể đặt mức độ ưu tiên theo nhu cầu của mình.

Xóa phần tử có mức ưu tiên cao nhất

2.5.1.Sự khác biệt giữa Hàng đợi ưu tiên và Hàng đợi thường

Trong một hàng đợi, quy tắc first-in-first-out được triển khai trong khi trong một hàng đợi ưu tiên, các giá trị được xóa dựa trên mức độ ưu tiên. Phần tử có mức độ ưu tiên cao nhất sẽ được xóa trước.

2.5.2.Triển khai hàng đợi ưu tiên

Hàng đợi ưu tiên có thể được triển khai bằng cách sử dụng một mảng, một danh sách liên kết, một cấu trúc dữ liệu heap hoặc một cây tìm kiếm nhị phân. Trong số các cấu trúc dữ liệu này, cấu trúc dữ liệu heap cung cấp một triển khai hiệu quả của hàng đợi ưu tiên.

Do đó, chúng ta sẽ sử dụng cấu trúc dữ liệu heap để triển khai hàng đợi ưu tiên trong hướng dẫn này. Max-heap được triển khai trong các hoạt động sau. Nếu bạn muốn tìm hiểu thêm về nó, vui lòng truy cập max-heap và min-heap.

Phân tích so sánh các triển khai khác nhau của hàng đợi ưu tiên được đưa ra bên dưới.

2.5.3.Hoạt động hàng đợi ưu tiên

Các hoạt động cơ bản của hàng đợi ưu tiên là chèn, xóa và xem trước các phần tử.

Trước khi nghiên cứu hàng đợi ưu tiên, vui lòng tham khảo cấu trúc dữ liệu heap để hiểu rõ hơn về heap nhị phân vì nó được sử dụng để triển khai hàng đợi ưu tiên trong bài viết này.

2.5.3.1. Chèn một phần tử vào hàng đợi ưu tiên

Việc chèn một phần tử vào hàng đợi ưu tiên (max-heap) được thực hiện theo các bước sau.

-Chèn phần tử mới vào cuối cây

Chèn một phần tử vào cuối hàng đợi

-Xếp chồng cây.

Xếp chồng sau khi chèn

2.5.3.2.Thuật toán chèn một phần tử vào hàng đợi ưu tiên (max-heap)

Nếu không có nút nào, 
  tạo một newNode.
else (một nút đã có sẵn)
  chèn newNode vào cuối (nút cuối cùng từ trái sang phải.)
  xếp chồng mảng
 

Đối với Min Heap, thuật toán trên được sửa đổi sao cho parentNode luôn nhỏ hơn newNode.

2.5.3.3. Xóa một phần tử khỏi hàng đợi ưu tiên

Việc xóa một phần tử khỏi hàng đợi ưu tiên (max-heap) được thực hiện như sau:

-Chọn phần tử cần xóa.

Chọn phần tử cần xóa

- Đổi nó với phần tử cuối cùng:

Hoán đổi với phần tử nút lá cuối cùng

- Xóa phần tử cuối cùng.

Xóa lá phần tử cuối cùng

- Xếp chồng cây.

Xếp chồng hàng đợi ưu tiên

Thuật toán xóa một phần tử trong hàng đợi ưu tiên (max-heap)

Nếu nodeToBeDeleted là leafNode
  xóa nút
Nếu không thì hoán đổi nodeToBeDeleted với lastLeafNode
  xóa noteToBeDeleted
   xếp chồng mảng
 

Đối với Min Heap, thuật toán trên được sửa đổi sao cho cả hai childNode đều nhỏ hơn currentNode.

2.5.3.4. Nhìn trộm từ Hàng đợi ưu tiên (Tìm max/min)

Hoạt động Peek trả về phần tử lớn nhất từ ​​Max Heap hoặc phần tử nhỏ nhất từ ​​Min Heap mà không xóa nút.

Đối với cả Max Heap và Min Heap

trả về rootNode

2.5.3.5.Trích xuất Max/Min từ Hàng đợi ưu tiên

Trích xuất Max trả về nút có giá trị lớn nhất sau khi xóa nó khỏi Max Heap trong khi Trích xuất-Min trả về nút có giá trị nhỏ nhất sau khi xóa nó khỏi Min Heap.

2.5.3.6.Triển khai hàng đợi ưu tiên trong Python, Java, C và C++

#Python

# Priority Queue implementation in Python

# Function to heapify the tree
def heapify(arr, n, i):
    # Find the largest among root, left child, and right child
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # Swap and continue heapifying if root is not the largest
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# Function to insert an element into the tree
def insert(array, newNum):
    size = len(array)
    if size == 0:
        array.append(newNum)
    else:
        array.append(newNum)
        for i in range((size // 2) - 1, -1, -1):
            heapify(array, size, i)

# Function to delete an element from the tree
def deleteNode(array, num):
    size = len(array)
    i = 0
    for i in range(0, size):
        if num == array[i]:
            break

    # Swap the element to delete with the last element
    array[i], array[size - 1] = array[size - 1], array[i]

    # Remove the last element (the one we want to delete)
    array.pop()

    # Rebuild the heap
    for i in range((len(array) // 2) - 1, -1, -1):
        heapify(array, len(array), i)

arr = []

insert(arr, 3)
insert(arr, 4)
insert(arr, 9)
insert(arr, 5)
insert(arr, 2)

print("Max-Heap array: " + str(arr))

deleteNode(arr, 4)
print("After deleting an element: " + str(arr))

#Java

// Priority Queue implementation in Java

import java.util.ArrayList;

class Heap {
  // Function to heapify the tree
  void heapify(ArrayList<Integer> hT, int i) {
    int size = hT.size();
    // Find the largest among root, left child and right child
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && hT.get(l) > hT.get(largest))
      largest = l;
    if (r < size && hT.get(r) > hT.get(largest))
      largest = r;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      int temp = hT.get(largest);
      hT.set(largest, hT.get(i));
      hT.set(i, temp);

      heapify(hT, largest);
    }
  }

  // Function to insert an element into the tree
  void insert(ArrayList<Integer> hT, int newNum) {
    int size = hT.size();
    if (size == 0) {
      hT.add(newNum);
    } else {
      hT.add(newNum);
      for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(hT, i);
      }
    }
  }

  // Function to delete an element from the tree
  void deleteNode(ArrayList<Integer> hT, int num) {
    int size = hT.size();
    int i;
    for (i = 0; i < size; i++) {
      if (num == hT.get(i))
        break;
    }

    int temp = hT.get(i);
    hT.set(i, hT.get(size - 1));
    hT.set(size - 1, temp);

    hT.remove(size - 1);
    for (int j = size / 2 - 1; j >= 0; j--) {
      heapify(hT, j);
    }
  }

  // Print the tree
  void printArray(ArrayList<Integer> array, int size) {
    for (Integer i : array) {
      System.out.print(i + " ");
    }
    System.out.println();
  }

  // Driver code
  public static void main(String args[]) {

    ArrayList<Integer> array = new ArrayList<Integer>();
    int size = array.size();

    Heap h = new Heap();
    h.insert(array, 3);
    h.insert(array, 4);
    h.insert(array, 9);
    h.insert(array, 5);
    h.insert(array, 2);

    System.out.println("Max-Heap array: ");
    h.printArray(array, size);

    h.deleteNode(array, 4);
    System.out.println("After deleting an element: ");
    h.printArray(array, size);
  }
}
 

#C

// Priority Queue implementation in C

#include <stdio.h>
int size = 0;
void swap(int *a, int *b) {
  int temp = *b;
  *b = *a;
  *a = temp;
}

// Function to heapify the tree
void heapify(int array[], int size, int i) {
  if (size == 1) {
    printf("Single element in the heap");
  } else {
    // Find the largest among root, left child and right child
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && array[l] > array[largest])
      largest = l;
    if (r < size && array[r] > array[largest])
      largest = r;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&array[i], &array[largest]);
      heapify(array, size, largest);
    }
  }
}

// Function to insert an element into the tree
void insert(int array[], int newNum) {
  if (size == 0) {
    array[0] = newNum;
    size += 1;
  } else {
    array[size] = newNum;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--) {
      heapify(array, size, i);
    }
  }
}

// Function to delete an element from the tree
void deleteRoot(int array[], int num) {
  int i;
  for (i = 0; i < size; i++) {
    if (num == array[i])
      break;
  }

  swap(&array[i], &array[size - 1]);
  size -= 1;
  for (int i = size / 2 - 1; i >= 0; i--) {
    heapify(array, size, i);
  }
}

// Print the array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i)
    printf("%d ", array[i]);
  printf("\n");
}

// Driver code
int main() {
  int array[10];

  insert(array, 3);
  insert(array, 4);
  insert(array, 9);
  insert(array, 5);
  insert(array, 2);

  printf("Max-Heap array: ");
  printArray(array, size);

  deleteRoot(array, 4);

  printf("After deleting an element: ");

  printArray(array, size);
}
 

#C++

// Priority Queue implementation in C++

#include <iostream>
#include <vector>
using namespace std;

// Function to swap position of two elements
void swap(int *a, int *b) {
  int temp = *b;
  *b = *a;
  *a = temp;
}

// Function to heapify the tree
void heapify(vector<int> &hT, int i) {
  int size = hT.size();
  
  // Find the largest among root, left child and right child
  int largest = i;
  int l = 2 * i + 1;
  int r = 2 * i + 2;
  if (l < size && hT[l] > hT[largest])
    largest = l;
  if (r < size && hT[r] > hT[largest])
    largest = r;

  // Swap and continue heapifying if root is not largest
  if (largest != i) {
    swap(&hT[i], &hT[largest]);
    heapify(hT, largest);
  }
}

// Function to insert an element into the tree
void insert(vector<int> &hT, int newNum) {
  int size = hT.size();
  if (size == 0) {
    hT.push_back(newNum);
  } else {
    hT.push_back(newNum);
    for (int i = size / 2 - 1; i >= 0; i--) {
      heapify(hT, i);
    }
  }
}

// Function to delete an element from the tree
void deleteNode(vector<int> &hT, int num) {
  int size = hT.size();
  int i;
  for (i = 0; i < size; i++) {
    if (num == hT[i])
      break;
  }
  swap(&hT[i], &hT[size - 1]);

  hT.pop_back();
  for (int i = size / 2 - 1; i >= 0; i--) {
    heapify(hT, i);
  }
}

// Print the tree
void printArray(vector<int> &hT) {
  for (int i = 0; i < hT.size(); ++i)
    cout << hT[i] << " ";
  cout << "\n";
}

// Driver code
int main() {
  vector<int> heapTree;

  insert(heapTree, 3);
  insert(heapTree, 4);
  insert(heapTree, 9);
  insert(heapTree, 5);
  insert(heapTree, 2);

  cout << "Max-Heap array: ";
  printArray(heapTree);

  deleteNode(heapTree, 4);

  cout << "After deleting an element: ";

  printArray(heapTree);
}
 

2.5.3.7.Ứng dụng hàng đợi ưu tiên

Một số ứng dụng của hàng đợi ưu tiên là:

1. Thuật toán Dijkstra
2. để triển khai ngăn xếp
3. để cân bằng tải và xử lý ngắt trong hệ điều hành
4. để nén dữ liệu trong mã Huffman

ĐỌC TOÀN BỘ CẤU TRÚC DỮ LIỆU & THUẬT TOÁN TẠI ĐÂY :

1.Cấu trúc dữ liệu và thuật toán -CHƯƠNG I :Giới thiệu DSA

2.Cấu trúc dữ liệu và thuật toán -CHƯƠNG I :Giới thiệu DSA (tiếp theo...)

3.Cấu trúc dữ liệu và thuật toán -CHƯƠNG I :Giới thiệu DSA (Phần 3...)

4.Cấu trúc dữ liệu và thuật toán -CHƯƠNG II CẤU TRÚC DỮ LIỆU-NGĂN XẾP

Đọc thêm về : 

5.DCT (Discrete cosine transform) biến đổi cosin rời rạc