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.
26 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a heap?
- A complete binary tree satisfying the heap property, commonly used to implement priority queues
- What is the heap property?
- Every parent node is greater than (max-heap) or less than (min-heap) its children
- What is a priority queue?
- 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?
- O(1), it is always at the root
- What is the time complexity of inserting a new element into a heap?
- O(log n)
- What is the time complexity of removing the root (min or max) from a heap?
- O(log n)
- What operation restores the heap property after insertion, moving a node upward?
- Sift-up (bubble-up)
- What operation restores the heap property after removal, moving a node downward?
- Sift-down (bubble-down, or heapify)
- What is heapify?
- 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)?
- O(n)
- How is a binary heap typically implemented, in terms of memory structure?
- 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?
- 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?
- (i-1)/2, using integer division
- What is heap sort?
- A sorting algorithm that builds a heap and repeatedly extracts the maximum (or minimum) element
- What is the time complexity of heap sort?
- O(n log n)
FlashKeepers