Binary Heap Flashcards
What is a binary heap?
A binary heap is a complete binary tree that satisfies the heap property, where every parent node is either greater than (max heap) or less than (min heap) its children.
What are the invariants of a binary heap?
Completeness: It is a complete binary tree, with all levels fully filled except possibly the last.
Heap Property:
In a min heap, each parent node is smaller than its children.
In a max heap, each parent node is larger than its children.
What is the primary difference between a min heap and a max heap?
In a min heap, the smallest element is at the root. In a max heap, the largest element is at the root.
Draw an example of a min heap.
10
/ \
15 30
/ \
40 50
Draw an example of a max heap.
50
/ \
30 20
/ \
10 15
What are the steps to delete the maximum element in a max heap?
Remove the root (maximum element).
Replace it with the last element in the heap.
Heapify down by comparing and swapping the new root with its larger child until the heap property is restored.
What is the heapsort algorithm?
Build a max heap from the unsorted array.
Swap the root (maximum element) with the last element.
Reduce heap size and heapify down.
Repeat until all elements are sorted.
What is the worst-case time complexity of HeapSort?
O(NlogN), because building the heap takes
O(N) and each extraction and heapification takes O(logN).
How does HeapSort compare to MergeSort and QuickSort?
HeapSort: O(NlogN) in both best and worst cases.
MergeSort: O(NlogN) in both best and worst cases.
QuickSort: O(NlogN) best-case, O(N ^2) worst-case without optimizations.
What is a priority queue?
A priority queue is a data structure where each element has a priority, and the element with the highest (or lowest) priority is dequeued first.
What are the main operations of a priority queue?
add(): Add an element with a priority.
get_max(): serves the element with the highest priority (removes it from the queue and returns it).
Name two scenarios where a priority queue is useful.
Task scheduling in operating systems, where high-priority tasks execute before lower-priority ones.
Dijkstra’s algorithm for finding the shortest path in graphs.
What is the best-case complexity for priority queue operations using a balanced BST?
O(logN) for insertion, deletion, and search.
What is the worst-case complexity for priority queue operations using an unbalanced BST?
O(N) for insertion, deletion, and search.
