Data Structures, unit: Heaps and Priority Queues. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a heap?
Show answer
A complete binary tree satisfying the heap property, commonly used to implement priority queues- What is the heap property?
Show answer
Every parent node is greater than (max-heap) or less than (min-heap) its children- What is a priority queue?
Show answer
An abstract data structure where each element has a priority, and higher-priority elements are served first- What is the time complexity of finding the minimum element in a min-heap?
Show answer
O(1), it is always at the root- What is the time complexity of inserting a new element into a heap?
Show answer
O(log n)- What is the time complexity of removing the root (min or max) from a heap?
Show answer
O(log n)- What operation restores the heap property after insertion, moving a node upward?
Show answer
Sift-up (bubble-up)- What operation restores the heap property after removal, moving a node downward?
Show answer
Sift-down (bubble-down, or heapify)- What is heapify?
Show answer
The process of converting an arbitrary array into a valid heap- What is the time complexity of building a heap from an unsorted array (heapify)?
Show answer
O(n)- How is a binary heap typically implemented, in terms of memory structure?
Show answer
As an array, using index arithmetic to represent parent-child relationships- In an array-based heap, what is the formula for finding a node's children given its index i?
Show answer
Left child at 2i+1, right child at 2i+2 (zero-indexed)- In an array-based heap, what is the formula for finding a node's parent given its index i?
Show answer
(i-1)/2, using integer division- What is heap sort?
Show answer
A sorting algorithm that builds a heap and repeatedly extracts the maximum (or minimum) element- What is the time complexity of heap sort?
Show answer
O(n log n)
FlashKeepers