Heaps

What two properties must a heap satisfy?

1. Shape property — must be a complete binary tree (all nodes at bottom level must be far left)
2. Ordering property — every node's label must be ≤ its children's labels

What does siftDown do and what is its precondition?

siftDown fixes a heap where only the root is out of place by repeatedly swapping it with its smaller child until it's in the correct position.
Precondition: both subtrees must already be valid heaps.

What does heapify do and how does it relate to siftDown?

heapify turns any complete binary tree into a heap by recursively heapifying the left and right subtrees first (satisfying siftDown's precondition), then calling siftDown on the root to finish.

How do changeToExtractionMode and removeFirst relate to heapify and siftDown?

They are general SortingMachine interface methods powered by heap-specific helpers.

• The code inside changeToExtractionMode will call heapify to do its work

• The code inside removeFirst will call siftDown to do its work

Explain the SortingMachine representation and be sure to differentiate between insertion & extraction mode

Private Comparator<T> machineOrder; – instance variable set by the constructor: determines ordering of T values. 

Private boolean insertionMode; – records whether "this" is in insertion mode 

Private Queue<T> entries; – holds entries of "this" while it is in insertion mode 

 

Private T[ ] heap; – holds entries of "this" while it is in extraction mode. 

Private int heapSize; – holds number of entries of "this" while it is in extraction mode

Break down the correspondence in your own words

Insertion mode (insertionMode = true):  

• the abstract value of this is represented by the ordering (machineOrder) and the multiset of entries stored in the entries queue. 

  • Entries come from the entries queue, not from the heap array

Extraction mode (insertionMode = false):  

• the abstract value of this is represented by the ordering (machineOrder) and the multiset of entries stored in heap[0, heapSize) 

  • The entries come from the heap array, not from the entries queue 

Break down the convention in your own words

If in insertion mode (insertionMode = true): 

• heapSize must be 0 (the heap array is not in use yet, so its size is zero) 

If in extraction mode (insertionMode = false), all of the following must hold: 

• entries queue must be empty (it's not being used in extraction mode) 

• Every position in the heap array must be non-null (no gaps or uninitialized slots) 

• The heap array from index 0 to heapSize - 1 must satisfy the heap property (as defined by SUBTREE_IS_HEAP, meaning every parent is ≤ its children according to machineOrder) 

• heapSize must be a valid index, i.e. between 0 and the length of the heap array inclusive