×

Courses

Chapters

>
<

Data Structure

Priority Queue | CrackEase

Priority Queue using Arrays

Implementation of Priority Queue using Arrays

Priority Queue is an abstract data type where each element has a priority. Elements are removed in order of priority (highest first for a max-priority queue). If two elements have the same priority, they are typically served in FIFO order.

Types of Priority Queue
  • Min Priority Queue: smallest value has highest priority.
  • Max Priority Queue: largest value has highest priority.

Common approaches

  • Ordered array: keep array sorted; enqueue is O(n), dequeue O(1).
  • Unordered array: append on enqueue O(1), dequeue requires scanning O(n) to find highest priority.
  • Binary heap: efficient heap-based implementation: enqueue (insert) and dequeue (extract) are O(log n).
Implementing Priority Queue (Unordered)

Below we show a heap-based implementation (max-heap) which is commonly used for priority queues. To switch to a min-heap, reverse comparison directions.

  • Enqueue: Insert element into heap — O(log n).
  • Dequeue: Remove element with highest priority (root) — O(log n).
  • Peek: Return root element — O(1).
priority queue diagram
Priority Queue – Heap-based (examples)
  
// Priority Queue implementation in C (heap-based)

#include <stdio.h>

int size = 0;

void swap(int *a, int *b) {
  int temp = *b;
  *b = *a;
  *a = temp;
}

// Heapify subtree rooted at index i for max-heap
void heapify(int array[], int n, int i) {
  int largest = i;
  int l = 2 * i + 1;
  int r = 2 * i + 2;

  if (l < n && array[l] > array[largest])
    largest = l;
  if (r < n && array[r] > array[largest])
    largest = r;

  if (largest != i) {
    swap(&array[i], &array[largest]);
    heapify(array, n, largest);
  }
}

// Insert element into heap (max-heap)
void insert(int array[], int newNum) {
  array[size] = newNum;
  size++;
  for (int i = size / 2 - 1; i >= 0; i--) {
    heapify(array, size, i);
  }
}

// Delete a specific element (value) from heap
void deleteRoot(int array[], int num) {
  int i;
  for (i = 0; i < size; i++) {
    if (num == array[i])
      break;
  }
  if (i == size) return; // not found

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

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

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);

  return 0;
}
  

  
// Priority Queue implementation in C++ (heap-based)

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

void swapVal(int *a, int *b) { int temp = *b; *b = *a; *a = temp; }

void heapify(vector &hT, int i) {
  int size = hT.size();
  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;
  if (largest != i) {
    swapVal(&hT[i], &hT[largest]);
    heapify(hT, largest);
  }
}

void insert(vector &hT, int newNum) {
  hT.push_back(newNum);
  for (int i = hT.size() / 2 - 1; i >= 0; i--) heapify(hT, i);
}

void deleteNode(vector &hT, int num) {
  int size = hT.size();
  int i;
  for (i = 0; i < size; i++) if (num == hT[i]) break;
  if (i == size) return;
  swapVal(&hT[i], &hT[size - 1]);
  hT.pop_back();
  for (int i = hT.size() / 2 - 1; i >= 0; i--) heapify(hT, i);
}

void printArray(const vector &hT) {
  for (int v : hT) cout << v << " ";
  cout << endl;
}

int main() {
  vector 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);
  return 0;
}
  

  
// Priority Queue implementation in Java (heap-based)

import java.util.ArrayList;

class Heap {
  void heapify(ArrayList hT, int i) {
    int size = hT.size();
    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;
    if (largest != i) {
      int temp = hT.get(largest);
      hT.set(largest, hT.get(i));
      hT.set(i, temp);
      heapify(hT, largest);
    }
  }

  void insert(ArrayList hT, int newNum) {
    hT.add(newNum);
    for (int i = hT.size() / 2 - 1; i >= 0; i--) heapify(hT, i);
  }

  void deleteNode(ArrayList hT, int num) {
    int size = hT.size();
    int i;
    for (i = 0; i < size; i++) if (num == hT.get(i)) break;
    if (i == size) return;
    hT.set(i, hT.get(size - 1));
    hT.remove(size - 1);
    for (int j = hT.size() / 2 - 1; j >= 0; j--) heapify(hT, j);
  }

  void printArray(ArrayList array) {
    for (Integer i : array) System.out.print(i + " ");
    System.out.println();
  }

  public static void main(String[] args) {
    ArrayList array = new ArrayList();
    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.print("Max-Heap array: "); h.printArray(array);
    h.deleteNode(array, 4);
    System.out.print("After deleting an element: "); h.printArray(array);
  }
}

Output : C

	
Max-Heap array: 9 5 4 3 2 
After deleting an element: 9 5 2 3

Output : C++

	
Max-Heap array: 9 5 3 4 2 
After deleting an element: 9 5 3 2

Output : Java

	
Max-Heap array: 9 5 3 4 2 
After deleting an element: 9 5 3 2
Footer Content | CrackEase
→
←