Heap

1. A heap is a container for objects that have keys. Supported Operations:

    a)  Insert ---- Add a new object to a heap. Running time : (O(logn))

 

    b)  Extract-Min ---- remove an object in heap with a minimum key value. Running time : (O(logn))

    c)  Heapfy ---- n batched Inserts in O(n) time.

    d)  Delete ---- delete an object from heap. Running time : (O(logn))

 

2. Canonical use of heap: fast way to do repeated minimum computations.

 

3. Application: Sorting

    SelectionSort : ~ O(n) linear scans, O(n^2) runtime on array of length n 

    Heap Sort : 1) insert all n array elements into a heap

                       2)  Extract-­Min to pluck out elements in sorted order 

    Running Time = 2n heap operations = O(nlog(n)) time.

 

4. Application: Event Manager

    “Priority Queue” – synonym for a heap.

    -- Objects = event records ( Action/update to occur at given time in the future )

    -- Key = time event scheduled to occur

    -- Extract-Min => yields the next scheduled event

 

5. Application: Median Maintenance

    Input: a sequence x1, x2, ..., xn of numbers, one-by-one 

    Output: at each step i , the median of {x1, .., xi}.

    Constraint: use O(log(i)) time at each step i.

    Solution: maintain heaps invariants

     a) Hlow = i/2 smallest elements and support Extract Max

     b) Hhigh = i/2 largest elements and support Extract Min

    Claim 1) can maintain invariants in O(log(i)) time

              2) given invariant, can compute median in O(log(i)) time

 

6. Heap Implementation:

    a) Think of a heap as a tree, rooted, binary, as complete as possible

    b) At every node x, Key[x] <= all keys of x’s children

    c) Object at root must have minimum key value

    d) Array Implementation: Parent(i) = floor(i/2) , Children(i) = 2i, 2i+1

    e) Insert (k)

        - stick k at end of last level.

        - Bubble-Up k until heap property is restored (key of k’s parent <= k)

     f) Extract-­Min

        - Delete root

        - Move last leaf to be new root.

        - Iteratively Bubble-Down until heap property has been restored [always swap with smaller child!]