Binary Heaps & Graphs as Data Structures

Two structures that look unrelated share a design philosophy: both maintain exactly as much information as their intended queries need, and no more.

A binary search tree maintains a total order, which is why it can answer any range query. A heap maintains only a partial order — every parent dominates its children, and nothing is known about siblings — which is why it cannot search but can produce the extreme element in constant time and restore itself in logarithmic time.

That deliberate weakness is what makes a heap cheap to maintain, and it is why a priority queue uses one rather than a search tree.

Graphs make a different version of the same trade, in the representation rather than the invariant. An adjacency matrix answers "is there an edge from $u$ to $v$" in constant time and costs $O(V^2)$ space. An adjacency list answers "what are $u$'s neighbours" in time proportional to the degree and costs $O(V+E)$ space.

Neither is better; density decides. A dense graph makes the matrix's space acceptable and its constant-time edge test valuable; a sparse graph makes the matrix mostly zeros and the list clearly superior.

1. The Heap Property

A binary heap is a complete binary tree — every level full except possibly the last, which fills from the left — satisfying a heap property.

In a max-heap, every node is greater than or equal to both its children. In a min-heap, every node is less than or equal to both.

Note what is not required. No relation is imposed between siblings, or between a node and its cousins. A heap is therefore far less ordered than a search tree, and that is deliberate: less order means less work to restore after a change.

Two immediate consequences are examined directly.

The root holds the extreme element, so finding the maximum in a max-heap is $O(1)$.

A heap cannot be searched efficiently. Locating an arbitrary key requires examining $O(n)$ nodes, because the partial order gives no guidance about which subtree to descend into.

The inorder traversal of a heap is not sorted, unlike that of a BST, and no traversal of a heap produces sorted order without doing the work of a sort.

2. The Array Representation

Because a heap is a complete tree, it can be stored in an array with no pointers at all — the tree structure is implicit in the indices.

For 0-based indexing:

$\text{left}(i)=2i+1\text{right}(i)=2i+2\text{parent}(i)=\lfloor \frac{i-1}{2}\rfloor$

For 1-based indexing the formulas are cleaner:

$\text{left}(i)=2i\text{right}(i)=2i+1\text{parent}(i)=\lfloor \frac{i}{2}\rfloor$

The convention must be checked from the question, because the two give different answers for the same index.

Two counting facts follow from completeness.

The last internal node is at index $\lfloor n/2\rfloor -1$ in 0-based indexing, so everything from there onward is a leaf.

A heap of $n$ nodes has $\lceil n/2\rceil$ leaves, which is why building a heap can skip half the array entirely.

The array representation is what makes heapsort in-place and what makes a heap the standard priority queue implementation: no allocation, no pointers, and perfect cache behaviour on the upper levels.

3. Heap Operations

Two repair operations do all the work, and every heap operation is one of them applied after a structural change.

Sift-up (percolate up) repairs a node that is too large for its position. Compare with the parent, swap if the heap property is violated, and repeat upward. It costs $O(\log n)$ because the path to the root has that length.

Sift-down (heapify) repairs a node that is too small. Compare with both children, swap with the larger, and repeat downward. It also costs $O(\log n)$.

Insertion appends at the first free position to preserve completeness, then sifts up. Extraction cannot simply remove the root, because that would break completeness, so the last element is moved to the root and sifted down.

4. Building a Heap

Given an arbitrary array, a heap can be built in two ways with different costs.

Inserting the $n$ elements one at a time costs $O(n\log n)$, since each insertion can sift up through the full height.

Sifting down from the last internal node to the root costs $O(n)$, which is asymptotically better and is the standard method.

The surprising bound deserves its argument. Sift-down at a node costs time proportional to that node's height, not the tree's. Most nodes are near the bottom and have tiny height: half the nodes are leaves and cost nothing, a quarter have height 1, an eighth have height 2.

Summing height times count over all levels gives

${\sum }_{h=0}^{\log n}\frac{n}{2^{h+1}}\times h=O(n)$

because the series $\sum h/2^h$ converges to a constant.

The intuition worth carrying is that the expensive nodes are rare. Only one node has the full height, and half the nodes have none at all.

5. Heapsort and Priority Queues

Heapsort builds a max-heap, then repeatedly swaps the root with the last element, shrinks the heap by one, and sifts down.

It runs in $O(n\log n)$ in all cases — best, average and worst — and sorts in place using only the original array plus a constant amount of extra space.

It is not stable, because sifting moves equal elements past each other unpredictably.

The comparison with quicksort and merge sort is the examined point. Quicksort is usually faster in practice despite an $O(n^2)$ worst case, because its inner loop is tighter and its memory access is more local. Merge sort is stable and predictable but needs $O(n)$ extra space. Heapsort is the one that guarantees $O(n\log n)$ in place, and it pays for that with poor cache behaviour, since sifting jumps across the array.

A priority queue is the heap's main application, supporting insert and extract-extreme in $O(\log n)$. It is the structure underneath Dijkstra's algorithm, Prim's algorithm, Huffman coding and event-driven simulation.

6. Graphs: Terminology and Counting

A graph is a set of vertices with a set of edges. The counting facts are asked directly.

An undirected simple graph on $n$ vertices has at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$ edges; a directed one has at most $n(n-1)$, since each ordered pair may have its own edge.

The sum of degrees is twice the edge count in an undirected graph, so the number of odd-degree vertices is even. In a directed graph, the sum of in-degrees equals the sum of out-degrees equals the edge count.

A graph is connected if a path exists between every pair. A directed graph is strongly connected if a directed path exists both ways between every pair, and weakly connected if the underlying undirected graph is connected.

A connected graph on $n$ vertices needs at least $n-1$ edges, achieved exactly by a tree, and a graph with $n$ vertices and more than $n-1$ edges must contain a cycle.

A graph with $n$ vertices and fewer than $n-1$ edges cannot be connected, which gives a fast elimination in many questions.

7. Graph Representations

The crossover is at $E\approx V^2$. A graph is dense when the edge count approaches the maximum, and sparse when it is closer to $V$.

Most real graphs — road networks, social graphs, web links — are sparse, which is why adjacency lists dominate in practice.

A useful matrix property is examined regularly: raising the adjacency matrix to the power $k$ gives, in entry $(i,j)$, the number of distinct walks of length exactly $k$ from $i$ to $j$.

For a weighted graph the matrix stores weights rather than 1s, with a sentinel such as infinity for absent edges, and the list stores pairs of neighbour and weight.

8. Traversals

Both traversals visit every reachable vertex once and cost the same.

Breadth-first search uses a queue and visits vertices in order of distance from the source. Depth-first search uses a stack, explicitly or through recursion, and goes as deep as possible before backtracking.

Both cost $O(V+E)$ with an adjacency list and $O(V^2)$ with a matrix, because listing a vertex's neighbours is what dominates.

Breadth-first search finds shortest paths in an unweighted graph, since it reaches every vertex by the fewest possible edges. It does not work for weighted graphs, which is exactly why Dijkstra's algorithm exists.

Depth-first search classifies each edge as it is explored, and the classification answers structural questions.

A directed graph has a cycle if and only if a depth-first search finds a back edge, which is the standard cycle-detection method and the basis of topological sorting.

In an undirected graph, only tree and back edges occur — forward and cross edges cannot arise, because an undirected edge to an already-visited vertex is always to an ancestor.

9. Worked Examples

Example 1. An array with 1-based indexing holds a max-heap. What are the indices of the parent, left child and right child of the element at index 7, in a heap of 20 elements?

With 1-based indexing, the parent of $i$ is $\lfloor i/2\rfloor$, the left child is $2i$ and the right child is $2i+1$.

Parent of 7: $\lfloor 7/2\rfloor =3$.

Left child: $2\times 7=14$.

Right child: $2\times 7+1=15$.

Both children exist because 14 and 15 are at most 20.

Under 0-based indexing the same element would sit at index 6, with parent $\lfloor 5/2\rfloor =2$, left child 13 and right child 14 — entirely different numbers for the same node, which is why the convention must be read from the question.

Example 2. Insert 45 into the max-heap [50, 30, 40, 10, 20, 35] using 0-based indexing. Show each swap.

Completeness requires appending at the first free position, index 6.

The array becomes [50, 30, 40, 10, 20, 35, 45].

Now sift up. The parent of index 6 is $\lfloor 5/2\rfloor =2$, holding 40. Since $45>40$, swap.

Array: [50, 30, 45, 10, 20, 35, 40]. The new element is now at index 2.

The parent of index 2 is $\lfloor 1/2\rfloor =0$, holding 50. Since $45<50$, the heap property holds and sifting stops.

The final heap is [50, 30, 45, 10, 20, 35, 40], after 2 comparisons and 1 swap.

Note that 45 ended above 30 despite 30 having been higher in the array, and no comparison between them ever occurred. That is the partial order at work: siblings and cousins are simply unrelated.

Example 3. Build a max-heap from [4, 10, 3, 5, 1] using the linear-time method, with 0-based indexing.

There are $n=5$ elements, so the last internal node is at index $\lfloor 5/2\rfloor -1=1$. Sift down from index 1 to index 0.

Index 1 holds 10, with children at indices 3 and 4 holding 5 and 1. The largest is 10 itself, so nothing moves.

Index 0 holds 4, with children at indices 1 and 2 holding 10 and 3. The largest child is 10, and $10>4$, so swap.

Array: [10, 4, 3, 5, 1]. The value 4 is now at index 1.

Continue sifting 4 down. Its children are at indices 3 and 4, holding 5 and 1. The largest is 5, and $5>4$, so swap.

Array: [10, 5, 3, 4, 1]. The value 4 is now at index 3, which is a leaf, so sifting stops.

The max-heap is [10, 5, 3, 4, 1].

Indices 2, 3 and 4 were never sifted from, which is exactly the saving: $\lceil 5/2\rceil =3$ of the 5 nodes are leaves and are already valid heaps of one element.

Example 4. Why is building a heap $O(n)$ rather than $O(n\log n)$?

The naive bound assumes every sift-down costs $\log n$. It does not: a sift-down from a node costs time proportional to the height of that node, and most nodes are shallow.

In a heap of $n$ nodes, roughly $n/2$ are leaves with height 0, $n/4$ have height 1, $n/8$ have height 2, and so on, with exactly one node at the full height.

The total work is the sum over heights of the number of nodes at that height times the height:

$T(n)={\sum }_{h=0}^{\log n}\frac{n}{2^{h+1}}\times h=\frac{n}{2}{\sum }_{h=0}^{\log n}\frac{h}{2^h}$

The series $\sum h/2^h$ converges to 2 as the upper limit grows, so the total is bounded by $n$.

The insight is that the expensive nodes are rare. Only the root can cost the full $\log n$, and the half of the array that costs nothing at all is skipped entirely.

Contrast this with inserting one at a time, which genuinely is $O(n\log n)$: each insertion sifts up from a leaf position, and leaf positions are exactly where the path to the root is longest.

Example 5. A simple undirected graph has 8 vertices. What is the maximum number of edges, and what is the minimum number for it to be connected? If it has 10 edges, must it contain a cycle?

The maximum is one edge per unordered pair: $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$ edges.

The minimum for connectivity is $n-1=7$ edges, achieved exactly by a spanning tree.

For the cycle question, recall that a connected acyclic graph on $n$ vertices has exactly $n-1$ edges. Any graph with more than $n-1$ edges must contain a cycle, regardless of connectivity, because each connected component with $k$ vertices can hold at most $k-1$ edges without a cycle, and summing over components gives at most $n-(\text{number of components})\le n-1$.

With 10 edges against a threshold of 7, the graph must contain a cycle — in fact at least 3 independent cycles, since the cycle count is $E-V+C$ where $C$ is the number of components, giving at least $10-8+1=3$.

Example 6. A directed graph is searched depth-first and a back edge is found. What does this prove, and what would the absence of any back edge prove?

A back edge leads from the current vertex to an ancestor still on the recursion stack.

That ancestor reached the current vertex by a directed path of tree edges, and the back edge returns directly to it. Together they form a directed cycle, so the presence of a back edge proves the graph is cyclic.

The converse also holds. If a directed graph contains a cycle, then during the depth-first search the first vertex of that cycle to be discovered will still be on the stack when the cycle's last edge is explored, so that edge is classified as a back edge.

So a directed graph is acyclic if and only if a depth-first search finds no back edge, which is the standard $O(V+E)$ cycle-detection method.

The absence of back edges therefore proves the graph is a directed acyclic graph, which in turn guarantees that a topological order exists — obtained by listing the vertices in reverse order of their depth-first finishing times.

Note that in an undirected graph the classification is simpler: only tree and back edges can occur, so a back edge to any vertex other than the immediate parent proves a cycle.

Summary

A heap maintains only a partial order — parent dominates children, siblings unrelated — which is why it cannot search but can restore itself in logarithmic time.

Completeness allows a pointerless array representation. Index formulas differ between 0-based and 1-based conventions, and the convention must be read from the question.

The last internal node is at $\lfloor n/2\rfloor -1$ in 0-based indexing, and $\lceil n/2\rceil$ of the nodes are leaves.

Every operation is a sift-up or a sift-down, each costing $O(\log n)$. Insertion appends then sifts up; extraction moves the last element to the root then sifts down.

Building a heap by sifting down from the last internal node costs $O(n)$, because sift-down cost is proportional to a node's height and most nodes are shallow. Inserting one at a time genuinely costs $O(n\log n)$.

Heapsort is $O(n\log n)$ in all cases and in place, but is unstable and has poor cache behaviour.

An undirected simple graph on $n$ vertices has at most $n(n-1)/2$ edges and needs at least $n-1$ to be connected. More than $n-1$ edges forces a cycle.

An adjacency matrix costs $O(V^2)$ space with a constant-time edge test; an adjacency list costs $O(V+E)$ with neighbour listing proportional to degree. Density decides.

The $k$-th power of the adjacency matrix counts walks of length $k$.

Breadth-first search uses a queue and gives shortest paths in unweighted graphs; depth-first search uses a stack and classifies edges. A directed graph is acyclic exactly when depth-first search finds no back edge, and undirected searches produce only tree and back edges.