Heaps, Priority Queues and Graph Representations: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 7, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A complete binary tree obeying a parent-child ordering rule, stored in an array. Insert and extract cost O(log n) while reading the extreme element costs O(1).
Heap order property
The invariant that every parent compares favourably with its children. It is far weaker than search order, so a heap gives fast extremes but no efficient search for arbitrary keys.
Max heap
A heap whose root holds the largest key, with each parent at least as large as its children. It supplies the repeated extraction step of heapsort.
Min heap
A heap whose root holds the smallest key. It is the workhorse behind shortest-path frontiers, event simulation and merging many sorted streams.
Sift up
Restoring the invariant after an insertion at the end by repeatedly swapping the new element with its parent while it compares better, costing at most the height of the heap.
Sift down
Restoring the invariant after the root is replaced by moving the element downward, swapping with its better child until both children compare worse, in O(log n) time.
Linear-time heap construction
Building a heap by sifting down every internal node from the bottom up costs Theta(n), not n log n, because most nodes sit near the leaves and move only a short distance.
Array embedding of a heap
Storing a complete tree so the children of index i sit at two times i plus one and two times i plus two, and the parent at the halved index, removing all pointer overhead.
Priority queue
An abstract type serving the highest-priority element next, with insert and extract as core operations. A binary heap is the standard implementation but not the only one.
Decrease key
Improving the priority of an element already stored, requiring a handle or index map to locate it. It costs O(log n) in a binary heap and O(1) amortized in a Fibonacci heap.
d-ary heap
A heap where each node has d children, making the tree shallower so insertion and priority improvement are cheaper, while extraction pays more comparisons per level.
Binomial heap
A forest of binomial trees supporting merge of two heaps in O(log n) time, which a plain binary heap cannot do without rebuilding from scratch.
Fibonacci heap
A lazy collection of trees giving O(1) amortized insert and priority improvement and O(log n) amortized extraction, which lowers the theoretical bound for shortest paths.
Meld operation
Combining two priority queues into one. Mergeable designs do it in logarithmic or constant time, whereas an array heap needs linear reconstruction.
Indexed priority queue
A heap paired with a map from element identity to array position, so an element's priority can be located and updated rather than reinserted as a duplicate.
Graph
A set of vertices with edges between them, modelling roads, dependencies, networks or states. Cost bounds are stated in terms of both the vertex count and the edge count.
Directed graph
A graph whose edges have an orientation, so reachability is asymmetric. Task scheduling, web links and state machines are naturally directed models.
Undirected graph
A graph whose edges are symmetric pairs, so an edge stored on one endpoint's list must be stored on the other's too, making the sum of all degrees twice the edge count.
Weighted graph
A graph carrying a numeric cost on each edge representing distance, time or capacity. Shortest-path and minimum-spanning problems are defined only for weighted graphs.
Adjacency matrix
A square table whose entry says whether an edge joins two vertices. Edge tests are O(1) but space is quadratic in the vertex count, so it suits dense graphs only.
Adjacency list
An array of per-vertex neighbour containers using space proportional to vertices plus edges. Traversal is efficient, but testing a specific edge costs time proportional to a degree.
Edge list
A flat collection of endpoint pairs with weights, the most compact form and the natural input to an algorithm that sorts edges globally rather than walking neighbourhoods.
Vertex degree
The number of edges touching a vertex, split into in-degree and out-degree when edges are oriented. Summing degrees over all vertices gives twice the undirected edge count.
Sparse versus dense graphs
A graph is sparse when its edge count is near its vertex count and dense when it approaches the square of the vertex count. The distinction decides which representation wins.
Self-loop and parallel edge
An edge joining a vertex to itself and two edges joining the same pair. Simple graph algorithms often assume neither exists, so inputs may need normalising first.