cs126 heaps

What is a heap?

• A binary tree storing keys at its nodes and satisfying the following properties:

  • Heap order

  • Complete binary tree

Define complete binary tree.

• For i = 0, …, h - 1: there are 2ⁱ nodes of depth i

• At depth h, the internal nodes are to the left of external nodes

Define heap order.

For every internal node, its key is greater than or equal to the key of its parent.

How can a priority queue be implemented using a heap?

Each internal node of the heap stores a (key,element) item.

What is the height of a heap storing n entries?

⌊logn⌋

Describe how an item k is inserted into a heap.

• Find the insertion node z (the new last node)

• Store k at z

• Restore the heap-order property (by upheap bubbling)

Describe how the smallest item is removed from a heap.

• Replace the root key with the key of the last node w

• Remove w

• Restore the heap-order property (by downheap bubbling)

Describe the upheap algorithm.

• Restores the heap-order property after a new element is added 

• Swaps k (the new node) along an upward path from the insertion node

• It terminates when the key k reaches:

  • The root

  • A node whose parent has a key smaller than or equal to k

What is the worst-case time cost of performing the upheap algorithm?

• O(log n)

• As a heap has height O(log n)

Describe the downheap algorithm.

• It restores the heap-order after the smallest item is removed

• Swaps the key k (the root) along a downward path from the root node

• Terminates when k reaches:

  • A leaf

  • A node whose children are greater than or equal to k

What is the worst-case time cost of performing the upheap algorithm?

• O(log n)

• As a heap has height O(log n)

Describe how a heap can be implemented using an array.

• For a heap with n keys, an array of length n is used

• For the node at index i:

  • Left child is at 2i + 1

  • Right child is at 2i + 2

  • Parent node is at index (i - 1)/2

What is a heap sort?

A sort when all elements are inserted in a heap, then removeMin() is called until all elements are removed (sorted).

What is the worst-case time cost of performing a heap sort?

O(nlogn)

What is the worst-case time cost of performing the priority queue method size() / isEmpty() / min() on a heap?

O(1)

What is the worst-case time cost of performing the priority queue method insert() on a heap?

O(n)

What is the worst-case time cost of performing the priority queue method removeMin() on a heap?

Describe the heapify algorithm.

• Starting at index i = (n - 1)/2

• Call downHeap() until i = 0, decrementing i at each step

heapify function proof?? what is its purpose? used in heap sort?