12 Heap

Based on complete binary trees

Types¶

Implementation¶

Array¶

1. Root = 0
2. Left Child = \(2i+1\)

Consider a node with index \(i\)

Linked List¶

Insertion¶

1. Find insertion point
2. Store there
3. Verify heap property
4. if not satisfied, up bubbling

Deletion¶

1. Remove the root element (We cannot remove a particular element)
2. Replace node with the last node of the subtree
3. Verify Heap property
4. if not satisfied, down bubbling

Heapification¶

up/down heap bubbling

1. compare 2 elements
2. swap if condition is not satisfied

void maxHeapify(int[] a, int n, int i)
{
  int largest = i, // assuming root is the largest
        l = (2*i) + 1,
        r = (2*i) + 2;

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

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

  if(largest != i)
    // swap root with largest node
    swap(a[i], a[largest])
}

Applications¶

1. Heap Sort
2. Order Statistics
3. Priority Queue

Priority Queue¶

• Max-Heap for max-priority queue
• Min-Heap for min-priority queue

Comments