Unit 3 : Heaps Flashcards
Heap Definition
structure property ( complete binary tree )
heap order property ( min/max heap )
each nodes children are larger than it.
Why is a Heap known as a priority queue?
numbers with more priority at the top of the heap
Describe several applications that use heaps
The priority of student registration
How are heaps implemented?
One-Dimensional array
Left child formula
Index * 2
Right child formula
Index * 2 + 1
parent formula
Index / 2
Steps for inserting an item onto a heap
Insert new node into next available slot, then percolate up until it fits in the heap.
Steps for deleting the minimum from a heap
Bring up the newest added node into the root, then percolate down the smaller child until it fits in the heap
Inserting into heap average runtime
O ( 1 )
Deleting minimum from heap runtime
average: O log n
Best: O ( 1 )
How does the heap sort work?
1) need a heap
2) initialize a standard array where the heap sort will take place
3) delete the min node from the heap, and shift that value to the end of the standard array
4) fix the heap and continue until no nodes remain
- THE RESULT IS A DESCENDING ORDER SORT
Heapsort runtime
O ( n log n )
What is a skew heap?
Heap with an order condition but no structure condition.
What is a skew heap used for?
Merging heaps
Steps for merging two skew heaps
1) Merge smaller root to right subtree of larger root
2) Merge smaller root subtree recursively
3) flag largest nodes on right paths, then twist entire tree. Do not twist flagged nodes and siblings. If a node has no sibling, do not twist.
What is a binomial queue?
Heap ordered forest that supports constant O ( 1 ) insertion time of another tree
What are the advantages of using a binomial queue?
constant insertion time of another binomial tree
Lossy vs Lossless file compression
Lossy file: some data is lost
Lossless: No data is lost
Why Is Huffman encoding a “greedy algorithm”?
The higher frequency nodes are closer to the top, ensuring they have smaller codes.
Greedy Algorithm
Attempts to always make right in selecting the smallest two
How is a heap array structured?
0 spot blank and 3 blank slots at the end.
nodes fill array from left to right
Skew Heaps twisting process runtime
O log n
How are binomial queues implemented?
Array of pointers to n-trees indexed by heights
How to keep constant insertion time in binomial queues?
Keep binomial queue sorted by height
Draw Binomial Queues
1) convert size to binary
2) use binary form to determine structure of forest
3) draw each tree so that each tree contains 2^h nodes where h is the height
4) use the binomial coefficient to determine how many nodes exist at each depth in the tree
Merge Binary Queues
1) Find combined size and convert to binary
2) use binary form to determine structure of new forest
3) merge all trees of the same height
4) if merged trees are same size of other trees, then merge again.
5) make sure new forest corresponds to the structure determined by the binary form
