Heapsort Flashcards
(20 cards)
What is a heap?
A complete binary tree where every node is greater than or equal to its children (max-heap).
What is a complete binary tree?
A binary tree where all levels are fully filled except possibly the last, which is filled from left to right with no gaps.
What is the heap property in a max-heap?
Every parent node is greater than or equal to its children.
What is the time complexity of getMax in a heap?
Θ(1) — the maximum is always at the root.
What is the time complexity of insert and deleteMax in a heap?
Θ(log n), due to sifting up or down.
What is the sift-down operation used for?
Restoring the heap after deleting the max by pushing the root down to its correct position.
What is the sift-up operation used for?
Restoring the heap after inserting a new element by bubbling it up to its correct position.
Why must a heap be a complete tree?
To allow efficient storage in an array without gaps and predictable child/parent indices.
What array indices correspond to a node’s children?
Left child = 2n + 1, right child = 2n + 2 (0-based indexing).
What index gives the parent of a node in a heap array?
Parent = floor((n - 1) / 2)
What is heapify?
The process of building a heap from an unsorted array using bottom-up sifting.
What is the time complexity of heapify?
Θ(n), due to the distribution of work among tree levels.
What is Heapsort?
A sorting algorithm that uses a heap to repeatedly extract the max and place it at the end of the array.
What is the time complexity of Heapsort?
Θ(n log n), and it uses no extra memory.
How does Heapsort relate to selection sort?
It repeatedly selects the maximum, but finds it efficiently using a heap.
Is Heapsort stable?
No, equal elements may not preserve their input order.
Why is the completeness of the tree crucial for array-based heaps?
Because it ensures all positions can be calculated without gaps, enabling efficient storage.
What operation allows priority adjustment in a heap?
increaseKey — it increases the priority and sifts the item to its correct position.
Why is a hashtable useful for implementing increaseKey?
It helps track the current index of each item in the heap for quick access.
What real-world problem can heaps solve efficiently?
Implementing priority queues, such as in scheduling or Dijkstra’s algorithm.
