Chapter 12: Heaps Flashcards
1
Q
How is a heap different from a binary search tree?
A
BST’s guarantees global order, where heaps only guarantee level orders
2
Q
When do you use a heap over a BST?
A
If you only care about min and max operations, BST’s are good at all finds (O(logn))
3
Q
How does heapsort work? (High-level)
A
Take unsorted array and insert into a heap. Removing from the heap will return items in a sorted order!
4
Q
What is the runtime of heapsort?
A
O(n log n)
5
Q
What is the run time of heap insert and remove?
A
O(log n)
