Lecture 9 - Heaps, Priority Queues, and Heapsort

Heaps support:

• Creation (from nothing or from existing data, as from an array)
• Insertion of elt
• Deletion of elt
• Search of element
• isEmpty()
• getMax()

Heaps: DS that give easy access to the most extreme elt, max or min usually

• Max Heap: heap with largest elt most extreme
• Min Heap: heap with smallest elt most extreme

Heaps use complete Binary trees as the underlying structure, often implemented using arrays

• NOT binary search trees

Undirected tree - 2 equivalent definitions:

1. Connected graphs w/ nodes and edges, w/o cycles

2. Graph where any 2 nodes are connected by unique shortest path

3. Root

4. Parent

5. Ancestor

6. Descendent

7. Internal node: node with children

8. Leaf node: node w/o children

Depth: depth(root) = 1; depth(node) = depth(parent) + 1

Height: height(leaf) = 1; height(node) = height(child) + 1

Max Height/Depth

Binary Tree: tree where every node has <=2 children

Complete Binary Tree: Binary tree, every level not including last, has to be filled, nodes are as far left as possible

Node Implementation

template <class Item>
struct Node {
    Node *left;
    Node *right;
    Item item;
    # Node *parent; or Node*previous;
}

Moving down a tree is efficient

Idea: Put nodes into array and access using int indices, pack a tree into array in regular way

Tree is Max Heap-Ordered if the key at each node is > keys of all node's children

Heap is a set of nodes with keys arranged in a complete heap-ordered tree, represent with array

Max-heap Property: no node in heap has key larger than root's key

Array/Vector implementation of Heap, at position i:

• Parent: floor(i / 2)
• Left Child: 2i

• Right Child: 2i + 1

• 0-indexed:

  • Parent: (i - 1) / 2

  • Left child: 2i + 1

  • Right child: 2i + 2

• Constant MAX_HEAP

• items: array of heap items

• size: # items in heap

• need to specify KEY and COMP function

• Duplicates are allowed in heaps?

Bottom-Up Fix-Up Example

• If element gets updated, heap may need to be shuffled around, within the behind the scenes vector

FIX UP
void fixUP(Item heap[], int k) {
    while(k > 1 && heap[k /2] < heap[k]) {   // first checks if k > 1, 
                                             // then checks if parent is less than child
        swap(heap[k], heap[k / 2]);
        k /= 2;
    }
}

Top-Down Fix-Down Example

• If you need to go down, Swap the parent with its larger child

FIX DOWN
void fixDown(Item heap[], int heapsize, int k) {
    // quick check
    while(2*k <= heapsize) {  // if you are more than halfway through the array, 
                              // you don't have children, skip half of the nodes
        int j = 2*k;   // left child
        if (j < heapsize && heap[j] < heap[j + 1]) ++j; // right child
        if (heap[k] >= heap[j]) break; // heap restored
        swap(heap[k], heap[j]);
        k = j; // move down the tree
    }
}

Heaps are really useful if you use them implement a Priority Queue, really a vector

Priority Queue:

1. Insertion
2. Removal

Insertion of (say, larger than root) item (INSERT)

1. push_back the largest item at the back, broken heap
2. fix up to restore heap order, log(n) insert

void insert(Item newItem) {
    heap[++heapsize] = newItem;   // heap.push
    fixUp(heap, heapsize);
}

Deletion of item

1. Swap max elt with last elt
2. call pop(), get rid of the last element (which is the max elt)
3. fix down

void popMax() {
    heap[1] = heap[heapsize];   // swap max and last elts
    fixDown(heap, heapsize - 1, 1);
}

How to build a Heap out of an array and int n?

Heapsort - gives you a sorted array:

1. Build Heap with Heapify
2. Fix Down the heap repeatedly, repeatedly dequeue the highest priority etl from a PQ

void heapsort(Item heap[], int n) {
    buildHeap(heap, n);   // Heapify, I think the commented code below is heapify, not sure
    /*
    //buildHeap(heap, n) {
        for (int i = n; i >= 1; --i) {   // start at bottom, skip half of nodes, fixDown in subtree
            fixDown(n, i);    // O(n), instead of O(n log n) with fixUp
        }
    //}
    */
    for (int i = n; i >= 2; --i) {
        swap(heap[i], heap[1]);   // swap with root, remove 1 elt from heap at a time?
        fixDown(heap, i - 1, 1);
    }
}

Heapsort O(n log n), each fixDown is log n, do it for n elements, n log n?