Binary Heap

Priority Queues are often implemented with a binary heap.

Nearly Complete binary tree is a binary tree in which all levels are “full”, except for possibly bottom level which is filled in from the left.

Each element in the array represents a tree node

Let's say elements are stored in A[1..heap-size].

  1. length: refers to the total number of elements that the array (which is being used to represent the binary heap) can hold. It's the maximum capacity of the array.

  2. heap-size: refers to the actual number of elements currently in the binary heap. It indicates how much of the array is currently being used to store the heap.

In a binary heap, heap-size is less than or equal to length. When the heap is full (i.e., when all available spaces are filled with valid data), heap-size equals length. When the heap is not full, heap-size is less than length.

Index rule:

Reference: http://users.cecs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module2/binary_heaps.xhtml

  • Root of tree = A[1]

  • Parent index of i index = i/2

  • Left index of i index = 2i

  • Right index of i index = 2i + 1

  • First leaf node = ⌊n/2⌋+1\lfloor n / 2\rfloor+1

Note: the number of leaves in a heap = n−⌊n/2⌋n-\lfloor{n/2}\rfloor which is ⌈n/2⌉\lceil{n/2}\rceil

The maximum height of a nearly complete tree containing n nodes:

log2nlog_2{n}

The number of nodes in a complete binary tree where all levels have the maximum number of nodes is 2h+1−12^{h+1}-1 where hhis the height of the tree.

Therefore the number of nodes of a nearly complete tree of height hh is 2h≤n≤2h+1−12^{\mathrm{h}} \leq \mathrm{n} \leq 2^{\mathrm{h}+1-1}

  • Maximum number of nodes: ∑i=0h2i=1−2h+11−2=−1+2h+11\sum_{i=0}^{h} 2^{i}=\frac{1-2^{h+1}}{1-2}=\frac{-1+2^{h+1}}{1}

  • Minimum number of nodes: 1+∑i=0h−12i=1+1−2h1−2=1+−1+2h11+\sum_{i=0}^{h-1} 2^{i}=1+\frac{1-2^{h}}{1-2}=1+\frac{-1+2^{h}}{1}

Binary Heap Data Structure:

  • A min binary heap (min-heap) is a complete binary tree in which every node satisfies the heap property: PARENT(A[i])≥A[i]PARENT(A[i])\geq A[i]

  • A max binary heap (max-heap) is a complete binary tree in which every node satisfies the heap property: PARENT(A[i])≤A[i]PARENT(A[i]) \le A[i]

Min-heap operations

MIN-HEAPIFY(A, i)

Percolate down by swapping with smaller child

This function always starts with an index of 1, and it maintains the heap order property. Essentially, if the priority of the parent item (identified by the index) is higher than that of its child item, the function compares the left and right children. Subsequently, it swaps the child with a lower key value than the key value at the given index. The time complexity for this operation is O(logn)O(logn), making it quite efficient.

MIN-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size and A[l] < A[i]
    smallest = l
else smallest = i
if r <= A.heap-size and A[r] < A[smallest]
    smallest = r
if smallest != i
    exchange A[i] with A[smallest]
    MIN-HEAPIFY(A, smallest)

HEAP-EXTRACT-MIN(A)

Delete minimum node and place last item in hole and percolate down

The function starts by removing the first element in the array. Before returning this element, it fills the now-empty spot with the last element from the heap tree. Following this, it calls upon the MIN-HEAPIFY function to reorder the element that has been moved to the first position, ensuring that it fits correctly within the heap tree's structure.

HEAP-EXTRACT-MIN(A)
if A.heap-size < 1
    error "heap underflow"
min = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1 # decrease the heap-size
MIN-HEAPIFY(A, 1)
return min

HEAP-DECREASE-KEY(A, i, key)

Percolate up

The process of "percolating up" through comparison with the parent and increasing the priority of a key at a certain index, works hand in hand with "MIN-HEAP-INSERT(A, key)". In the latter, the heap size is increased and "HEAP-DECREASE-KEY(A, heap-size, key)" is called to meet the heap property. These two procedures function as a pair in managing the heap.

HEAP-DECREASE-KEY(A, i, key)
if key > A[i]
    error "new key is larger"
A[i] = key
while i > 1 and A[PARENT(i)] > A[i]
    exchange A[i] with A[PARENT(i)]
    i = PARENT(i)
MIN-HEAP-INSERT(A, key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = inf
HEAP-DECREASE-KEY(A, A.heap-size, key)

BUILD-MIN-HEAP(A)

Percolate down

The process begins from the parent of the last node and swaps nodes in reverse level order. For each swap, it descends to the very bottom of the structure, carrying out the swaps along the way. The time complexity of this operation is O(n)O(n)

  • Amortized analysis: determine worst-case running time of a sequence of data structure operations as a function of the input size.

  • Aggregate method: sum up sequence of operations, weighted by their cost.

BUILD-MIN-HEAP(A)
A.heap-size = A.length
for i = floor(A.length/2) downto 1
    MIN-HEAPIFY(A, i)

More to learn?

Last updated