Heaps

A heap is a complete tree with an ordering-relation R holding between each node and its descendant.

Examples for R: smaller-than, bigger-than

Assumption: In what follows, R is the relation ‘bigger-than’, and the trees have degree 2.

Heap	Not a heap

Adding an Element

1. Add a node to the tree
   
2. Move the elements in the path from the root to the new node one position down, if they are smaller than the new element

   new element	4	7	9
   modified tree
3. Insert the new element to the vacant node
4. A complete tree of n nodes has depth log n, hence the time complexity is O(log n)

Deleting an Element

1. Delete the value from the root node, and delete the last node while saving its value.

   before	after
2. As long as the saved value is smaller than a child of the vacant node, move up into the vacant node the largest value of the children.
    
3. Insert the saved value into the vacant node
   
4. The time complexity is O(log n)

Initialization

Brute Force

Given a sequence of n values e₁, ..., e_n, repeatedly use the insertion module on the n given values.

• Level h in a complete tree has at most 2^h-1 = O(2ⁿ) elements
• Levels 1, ..., h - 1 have 2⁰ + 2¹ +  + 2^h-2 = O(2^h) elements
• Each element requires O(log n) time. Hence, brute force initialization requires O(n log n) time.
  elements.

Efficient

• Insert the n elements e₁, ..., e_n into a complete tree
  
• For each node, starting from the last one and ending at the root, reorganize into a heap the subtree whose root node is given. The reorganization is performed by interchanging the new element with the child of greater value, until the new element is greater than its children.
  
  
  
  
• The time complexity is O(0 * (n/2) + 1 * (n/4) + 2 * (n/8) +  + (log n) * 1) = O(n(0  2^-1 + 1  2^-2 + 2  2^-3 +  + (log n)  2^- log n)) = O(n)
  since the following equalities holds.  _{k = 1}(k - 1)2^-k =2[ _{k = 1}(k - 1)2^-k] - [ _{k = 1}(k - 1)2^-k] =[ _{k = 1}k2^-k] - [ _{k = 1}(k - 1)2^-k] = _{k = 1}[k - (k - 1)]2^-k = _{k = 1}2^-k =1

Applications

Priority Queue A dynamic set in which elements are deleted according to a given ordering-relation.

Heap Sort Build a heap from the given set (O(n)) time, then repeatedly remove the elements from the heap (O(n log n)).

Implementation

An array. The root is at location 1. Location i > 1 is a child of i/2.