[Algorithm] Priority Queue and Heap

Priority Queue

• Similar to a regular queue(FIFO)
• The key difference is that each element has a priority
  • An element with high priority is served before an element with low priority
• A priority queue possesses the following attributes:
  • Every item has a priority.
  • Items with higher priority are dequeued before items with lower priority.
  • If two items have the same priority, they are dequeued based on their order in the queue.
• Time complexity:

Implementation method	enqueue	dequeue	search max
unsorted array	O(1)	O(N)	O(N)
unsorted linked list	O(1)	O(N)	O(N)
sorted array	O(N)	O(1)	O(1)
sorted linked list	O(N)	O(1)	O(1)
max heap	O(log2N)	O(log2N)	O(1)

Because the heap method guarantees O(logN) even in the worst case, heap is commonly employed for implementation.

• Using an unsorted array/linked list
  • Insert elements to the last position.
  • Search an element with the highest priority sequentially.
• Using a sorted array/linked list
  • Insert an element by descending order.
  • Search the first element simply.
• Heap-basd implementation

#include "Heap.h"

typedef Heap PQueue;

void InitPQueue(PQueue* ppqueue);
bool IsPQEmpty(PQueue* ppqueue);
bool IsPQFull(PQueue* ppqueue);

void Enqueue(PQueue* ppqueue, Data data, int priority);
Data Dequeue(PQueue* ppqueue);

void InitPQueue(PQueue* ppqueue){
	InitHeap(ppqueue);
}

bool IsPQEmpty(PQueue* ppqueue){
	return IsEmpty(ppqueue);
}

bool IsPQFull(PQueue* ppqueue){
	return IsFull(ppqueue);
}

void Enqueue(PQueue* ppqueue, Data data, int priority){
	Insert(ppqueue, data, priority);
}

Data Dequeue(PQueue* ppqueue){
	return Delete(ppqueue);
}

 

Heap

• Complete binary tree
• Max heap : The value of root is the maximum in the tree.
• Min heap: The value of root is the minimum in the tree.
• The subtrees are also heaps: key(parent) >= key(child)
• Given the heap has n nodes, its height is O(log2n)
  • A complete binary tree holds.
  • For each level i, 2^i nodes exist except for the level.
• Array-based implementation
  • Because heap is a complete binary tree, each node has an index in sequence.
  • Suppose that the index of a node is x.
    • Index of a left-child node: 2x
    • Index of a right-child node: 2x +1

#define MAX_HEAP 100

typedef enum {false, true} bool;
typedef char Data;

typedef struct {
	Data data;
    int priority;
} HNode;

typedef struct {
	HNode items[MAX_HEAP + 1];
    int num;
} Heap;

// Make a heap empty.
void InitHeap(Heap *pheap);
// check whether a heap is empty. 
bool IsEmpty(Heap *pheap);
// Check whether a heap is full. 
bool IsFull(Heap *pheap);

// Insert a node to the heap.
void Insert(Heap *pheap, Data data, int priority); 
// Remove the maximum data from the heap.
Data Delete(Heap *pheap);

// Get a parent index for a given index.
int GetParent(int idx);
// Get a left child index for a given index.
int GetLChild(int idx);
// Get a right child index for a given index.
int GetRChild(int idx);
// Get a child index with high priority between two child nodes. 
int GetHighPrioityChild(Heap* pheap, int idx);


void InitHeap(Heap *pheap){
	pheap->num = 0;
}

bool IsEmpty(Heap *pheap){
	return pheap->num == 0;
}

bool IsFull(Heap *pheap){
	return pheap->num == MAX_HEAP;
}

int GetParent(int idx){
	return idx / 2;
}

int GetLChild(int idx){
	return idx * 2;
}

int GetRChild(int idx){
	return idx * 2 + 1;
}

int GetHighPriorityChild(Heap *pheap, int idx){
	if(GetLChild(idx) > pheap->num)
    	return 0;
    else if (GetLChild(idx) == pheap->num)
    	return GetLChild(idx)
    else{
    	int left = GetLChild(idx), right = GetRChild(idx);
        if (pheap->items[left].priority > pheap->item[right].priority)
        	return left;
        else
        	return right;
    }
}

• Insertion in Heap
  1. Inserting a new node
     • Insert a new node into a bottom-rightmost leaf node available.
  2. Updating the node
     • Compare the new node with its parent.
       • if the new node is higher priority than its parent, exchange them.
     • Do this until the new parent is greater than the new node or the new node becomes the root

void insert(Heap *pheap, Data data, int priority){
	HNode newNode;
    int idx = pheap->num + 1;
    if (IsFull(pheap)) exit(1);
    
    while (idx > 1){
    	int parent = GetParent(idx);
        if (priority > pheap->items[parent].priority){
        	pheap->items[idx] = pheap ->items[parent];
            idx = parent;
        }
        else break;
    }
    newNode.data = data;
    newNode.priority = priority;
    
    pheap->items[idx] = newNode;
    pheap->num++;
}

• Deletion in Heap
  1.  Removing the root from the heap
     • Remove the max node from the root of the heap.
     • Place the last node to the root
  2. Updating the heap
     • Compare the root with its children.
       • If it is smaller than any of children, exchange the position with its max child.
     • Do this until the heap is reestablished.

Data Delete(Heap *pheap){
	Data max = pheap->items[1].data;
    HNode last = pheap->items[pheap->num];
    int parent = 1, child;
    
    while (child = GetHighPriorityChild(pheap, parent)) {
    	if(last.priority < pheap->items[child].priority){
        	pheap->items[parent] = pheap->items[child];
            parent = child;
        }
        else break;
    }
    
    pheap->items[parent] = last;
    pheap->num--;
    
    return max;
}

• Heap Sort (sorting elements by using a max heap)
  
  1. Inserting each element to the heap
  2. Removing all elements from the heap in sequence
     • when deleting elements, it ensures to return the maximum element.

void HeapSort(Data a[], int n){
	Heap heap;
    InitHeap(&heap);
    
    // Insert all elements to the heap
    for (int i = 0; i < n; i++)
    	Insert(&heap, a[i], a[i]);
    
    // Remove all elements from the heap
    for (int i = n - 1; i >= 0; i--)
    	a[i] = Delete(&heap);
}