SUNY Geneseo Department of Computer Science

Introduction to Heaps

Return to List of Lectures

Misc

SOFIs

• On-line
• Now through May 2
• Check e-mail or see https://www.onlinecourseevaluations.com/login.aspx?s=geneseo
• 1 response already

Questions?

Heaps

Read Section 14.4 intro (pp 493 bottom to 494)

• and 14.4.1 (pg 494)
• and 14.4.4 up to but not including "Insertion" (pp 497 bottom to 500 top)
• Priority queue isn't based on time but on value/priority
• Main methods
  • Add item
    • Precondition: properly formed priority queue, i item
    • Post: queue still properly formed, contains i
  • Retrieve by priority - retrieves highest-priority item
• Balanced trees can create heaps
  • Root is highest priority
  • Children are lower priority
  • i.e., root in each subtree is highest priority
• Algorithm to delete from heap
  • Remove root
  • Find element at bottom to move to root
  • Sift down until order OK
• Total time is Θ( logn )

Two kinds of heap

• Min-heap = heap ordered so that smallest values towards root
• Max-heap = ordered with large values towards root

Examples

• Build a min-heap from 6, 2, 8, 4, 3, 9

Try to develop algorithm(s) for inserting a new value into a heap.

    insert( v )
        make node from v
        make this node a leaf of heap, in available spot closest to root
        while v is less than parent (and v has a parent)
            swap with parent

• Note that loop here has invariant that subtree rooted at v is a heap; that implies that whole tree is a heap when loop exits because either loop exits with v at root of whole tree, or fact that whole tree was a heap initially and subtree rooted at v is too, with v greater than or equal to its parent, implies that whole tree is a heap again.

    insert2( v )
        if ( ! this.isEmpty() )
            if ( v >= this.value )
                if ( putleft )
                    putleft = left.insert(v )
                    return true
                else 
                    putleft = ! right.insert( v )
                    return false
            else
                swap v with this.value
                this.insert( v )        // this is the old root value after swap
        else
            this.value = v; left = right = empty heap
            return false

• You can insert either from bottom or top!

First version of "insert" above is pretty solid, but requires finding the empty leaf position "closest to root." This is a well-defined notion if the heap is a "complete" tree.

• "Complete" tree has all levels except the lowest filled, and all nodes in the lowest level at the left side:

Hand out Problem Set 13

Next

Representing complete trees

Read section 14.2.4