Tree and Heap Basics

1Introduction

This lecture defines parent-child relationships and depth in rooted trees and explains the invariant, basic operations, and complexity of binary heaps.

2Rooted trees

A tree is an undirected graph in which there is exactly one path between every pair of vertices. A rooted tree designates one vertex of a tree as its root. For each non-root vertex $$v$$v, the parent of $$v$$v is the vertex immediately after $$v$$v on the path from $$v$$v to the root. A vertex whose parent is $$v$$v is a child of $$v$$v. The root has no parent.

The depth of a vertex $$v$$v is the number of edges on the path from the root to $$v$$v. The root has depth $$0$$0, and a child has depth one greater than its parent. The height of a tree is the maximum depth of its vertices. A rooted tree in which every vertex has at most two children is a binary tree.

3Binary heaps

A complete binary tree with $$n$$n elements has every level except possibly the last filled, and its last-level vertices occupy consecutive positions from the left. Its height is $$\lfloor {\log }_{2}n\rfloor$$\lfloor\log_2 n\rfloor for $$n>0$$n>0. It can be stored in level order in an array indexed from $$0$$0, where the children of index $$i$$i have indices $$2i+1$$2i+1 and $$2i+2$$2i+2.

A min-heap has the shape of a complete binary tree and satisfies

for every edge. This heap invariant places an element with a minimum key at the root: applying the inequalities transitively along the path from the root to any vertex shows that the root key is no greater than that vertex's key. The invariant does not order siblings or vertices in different subtrees. A max-heap reverses the inequality.

4Basic operations and complexity

• Finding the minimum examines the root and therefore takes $$\mathrm{\Theta }\left(1\right)$$\Theta(1) time. Accessing an empty heap violates a precondition.
• Insertion appends an element and swaps it with its parent while its key is smaller. Before a swap, only the edge from the inserted element to its parent can violate the invariant. Each swap moves this possible violation toward the root, so the invariant is restored when the process stops. If one level of swapping takes $$O\left(1\right)$$O(1) time, the worst-case time is $$O\left(\log n\right)$$O(\log n).
• Deleting the minimum requires a nonempty heap. If $$n=1$$n=1, remove the root and leave an empty heap. If $$n>1$$n>1, remove the root and move the last element to the root. While a child exists with a key smaller than the current element, swap the current element with the minimum-key child among the children that exist. On termination the invariant also holds between the current element and its children, while all untouched edges have preserved it. The worst-case time is $$O\left(\log n\right)$$O(\log n).

A min-heap can implement a priority queue, an abstract data type that supports insertion and access to or deletion of an element with minimum priority. A heap does not maintain all elements in sorted order, so it does not necessarily provide fast search for an arbitrary key.