SUNY Geneseo Department of Computer Science

Heap Insertion

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
• ? responses now

Final exam

• Thursday, May 3, 8:00 AM
• Comprehensive but emphasizing material since last hour exam
• Designed for 2 hours, you have 3
• Otherwise similar rules and format to hour exams
• Donuts and cider

Problem Set 14 due today

Questions?

Heap Insertion

Finish section 14.4, from "Insertion" (page 500) through end (page 503)

• Insertion algorithm
  • Add new node to first available leaf position from left to right
  • (And then sift that node up the tree until heap order restored)
• Use array implementation of tree
• Constructing heap from many elements rather than 1 by 1
  • Faster than n logn for adding 1 by 1
  • Θ(n) instead
• Can also compare nodes by age after priority

Flesh out the bottom-up insertion algorithm in terms of a tree in an array

    // in class MaxHeap<E extends Comparable<...> >
    private E[] elements              // 0-origin
    private int n

    insertBottomUp( v )
        elements[n] = v
        n = n + 1
        i = n - 1
        while ( (i-1)/2 >= 0 && elements[i] > elements[ (i-1)/2 ] )
            swap( i, (i-1)/2 )
            i = (i-1)/2

    void swap( int a, int b )
        E x = elements[a]
        elements[a] = elements[b]
        elements[b] = x

• Analog of "while" that sifts down
  • Mini-assignment

Swap and object representation

Next

Finish heap insertion and deletion algorithms.

Mini-assignment above re sifting down.