Binary Heap

• Figure 6.1 Basic model of a priority queue

  
• Priority queues are important in the implementation of greedy algorithms, which operate by repeatedly finding a minimum
• In this chapter we will see a use of priority queues in discrete event simulation

  
• Simple linked list implementation of priority queue

  Insertions at the front in O(1), traversing the list to delete the minimum in O(N)

  
• Sorted linked list implementation of priority queue

  Insertions expensive (O(N)), deleteMins cheap (O(1))

  
• Binary search tree implementation of priority queue

  O(log N) average running time for both insertions and deletions
• Using a search tree could be overkill because it supports a host of operations that are not required
• Binary heap


  The basic data structure used, supports both insert and deleteMin in O(log N) worst-case time
• Binary heap


  • Structured as a complete binary tree
  • Satisfies the heap-order property (parent key is smaller than child keys)
• A complete binary tree of height h has between 2^h and 2^(h+1) - 1 nodes

  
• The height of a complete binary tree is log N
• A complete binary tree can be represented in an array with no links required

  
• For any element in array position i, the left child is in position 2i, the right child is in 2i+1, and the parent is in i/2
• Heap-order property


  For every node X, the key in the parent of X is smaller than (or equal to) the key in X, with the exception of the root
• Inserting into a binary heap

  1. Create a hole in the next available location

  2. If the element to be inserted violates the heap-order property, slide the element in the hole's parent node into the hole

  3. Repeat this process until the element can be placed in the hole
• Deleting the minimum from a binary heap

  1. Remove the minimum element at the root, creating a hole

  2. Place the last element in the heap into the hole

  3. If the last element violates the heap-order property, slide the smaller of the hole's children into the hole

  4. Repeat this process until the last element can be placed in the hole
• Placing X in its correct spot along a path from the root containing minimum children


  1. Push the hole down one level

  2. Repeat until X can be placed in the hole
• Percolate down is used to avoid the use of swaps in the deleteMin routine.
• A frequent implementation error in heaps occurs when there are an even number of elements in the heap, and the one node that has only one child is encountered.
• You must make sure not to assume that there are always two children, so this usually involves an extra test.
• One extremely tricky solution is always to ensure that your algorithm thinks every node has two children. Do this by placing a sentinel, a value higher than any in the heap, at the spot after the heap ends, at the start of each percolate down when the heap size is even.
• This eliminates the need to test for the presence of a right child, but you cannot eliminate the requirement that you test when you reach the bottom, because this would require a sentinel for every leaf.
• The worst-case running time for the deleteMin operation is O(log N).
• On average, the element that is placed at the root is percolated almost to the bottom of the heap (which is the level it came from), so the average running time is O(log N).
• A heap designed to find the minimum element (also known as a (min) heap) is of no help whatsoever in finding the maximum element.
• A heap has very little ordering information, so there is no way to find any particular element without a linear scan through the entire heap.
• If it is important to know where elements are, some other data structure, such as a hash table, must be used in addition to the heap.
• decreaseKey(p, Δ) operation


  1. Lowers the value of the item at position p by a positive amount Δ

  2. Fixes the heap order by a percolate up
• increaseKey(p, Δ) operation


  1. Increases the value of the item at position p by a positive amount Δ

  2. Done with a percolate down
• delete(p) operation


  1. Removes the node at position p from the heap

  2. Done by first performing decreaseKey(p, ∞) and then performing deleteMin()
• buildHeap


  1. Places N items into a heap

  2. Done by placing the N items into the tree in any order, maintaining the structure property

  3. Then percolateDown(i) percolates down from node i
• The sum of the heights of all the nodes in a perfect binary tree of height h containing 2^h - 1 nodes is 2^(h+1) - 1 - (h + 1).
• For a complete tree with N = 2^h nodes, the sum of the heights can be shown by induction to be N - b(N), where b(N) is the number of 1s in the binary representation of N.