SUNY Geneseo Department of Computer Science

Sifting Down in Heaps

Return to List of Lectures

Misc

CSci end-of-semester mixer

• Tuesday, May 1, 12:00 - whenever
• South 309

SOFIs

• On-line
• Now through May 2
• Check e-mail or see https://www.onlinecourseevaluations.com/login.aspx?s=geneseo
• 4 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

Questions?

Heap Insertion and Deletion

Pseudocode

    // 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

Red text = "sift up" algorithm

Mini-Assignment: "sift-down" algorithm (which turned into a full-blown deletion algorithm)

    public void delete( int v )
        elements[v] = elements[n-1]
        elements[n-1] = null
        n = n - 1
        int p = v
        while ( p <= (n-2)/2 && elements[p] < elements[ largestChild(p) ] ) {
            swap( p, largestChild(p) )
            p = largestChild(p)
        }

    int largestChild( int p )           // return index of largest child
        // precondition: p has at least one child
        if ( p == (n-2)/2 || elements[2*p + 1] > elements[2*p + 2] )
            return 2 * p + 1
        else
            return 2 * p + 2

Next

Priority queues (as distinct from heaps)