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