Template:Computer Science:Data Structures:Min and Max Heaps

Min and Max Heaps

A heap is an efficient semi-ordered data structure for storing a collection of orderable data. A min-heap supports two operations:

  INSERT(heap, element)
  element REMOVE_MIN(heap)

(we discuss min-heaps, but there's no real difference between min and max heaps, except how the comparison is interpreted.)

This chapter will refer exclusively to binary heaps, although different types of heaps exist. The term binary heap and heap are interchangeable in most cases. A heap can be thought of as a tree with parent and child. The main difference between a heap and a binary tree is the heap property. In order for a data structure to be considered a heap, it must satisfy the following condition (heap property):

If A and B are elements in the heap and B is a child of A, then key(A) ≤ key(B).

(This property applies for a min-heap. A max heap would have the comparison reversed). What this tells us is that the minimum key will always remain at the top and greater values will be below it. Due to this fact, heaps are used to implement priority queues which allows quick access to the item with the most priority. Here's an example of a min-heap:

A heap is implemented using an array that is indexed from 1 to N, where N is the number of elements in the heap.

At any time, the heap must satisfy the heap property

  array[n] <= array[2*n]

and

  array[n] <= array[2*n+1]

whenever the indices are in the arrays bounds.

Compute the extreme value

We will prove that $array[1]$ is the minimum element in the heap. We prove it by seeing a contradiction if some other element is less than the first element. Suppose array[i] is the first instance of the minimum, with $array[j]>array[i]$ for all $j<i$, and $i\ge 2$. But by the heap invariant array, $array[floor(i/2)]<=array[i]$: this is a contradiction.

Therefore, it is easy to compute $MIN(heap)$:

  MIN(heap)
     return heap.array[1];

Removing the Extreme Value

To remove the minimum element, we must adjust the heap to fill $heap.array[1]$. This process is called percolation. Basically, we move the hole from node i to either node $2i$ or $2i+1$. If we pick the minimum of these two, the heap invariant will be maintained; suppose $array[2i]<array[2i+1]$. Then $array[2i]$ will be moved to array[i], leaving a hole at $2i$, but after the move $array[i]<array[2i+1]$, so the heap invariant is maintained. In some cases, $2i+1$ will exceed the array bounds, and we are forced to percolate $2i$. In other cases, $2i$ is also outside the bounds: in that case, we are done.

Ignore remove algorithm, I'm 100% sure it won't work. Therefore, here is the remove algorithm:

 REMOVE_MIN(heap)
   return_value = heap.array[1];
   hole_index = 1;
   while (hole_index < heap.array.len) {
     if (2 * hole_index > heap.array.len)
       break;
     if (2 * hole_index + 1 > heap.array.len)
       {
         heap.array[hole_index] = heap.array[2*hole_index];
         hole_index = 2 * hole_index;
       }
     else
       {
         if (heap.array[2*hole_index] < heap.array[2*hole_index+1])
           new_hole_index = 2 * hole_index;
         else
           new_hole_index = 2 * hole_index + 1;
         heap.array[hole_index] = heap.array[new_hole_index];
         hole_index = new_hole_index;
       }
    }
   heap.array.len -= 1;

Inserting a value into the heap

A similar strategy exists for INSERT: just append the element to the array, then fixup the heap-invariants by swapping. For example if we just appended element N, then the only invariant violation possible involves that element, in particular if $array[floor(N/2)]>array[N]$, then those two elements must be swapped and now the only invariant violation possible is between

 array[floor(N/4)]  and  array[floor(N/2)]

we continue iterating until N=1 or until the invariant is satisfied.

INSERT(heap, element)
   append(heap.array, element)
   i = heap.array.length
   while (i > 1)
     {
       if (heap.array[i/2] <= heap.array[i])
         break;
       swap(heap.array[i/2], heap.array[i]);
       i /= 2;
     }

TODO

 Make-heap: it would also be nice to describe the O(n) make-heap operation
 Heap sort: the structure can actually be used to efficiently sort arrays
 Treaps: heaps where elements can be deleted by name