## 7.6.1 Heaps and Basic Heap Routines Recall that the depth of a node in a tree is the number of edges in the unique path from the root to that node, the depth *d* of a tree is the maximum depth of all nodes in the tree, and a leaf in a tree is any node with no children (see [Section 3.5](LiB0029.html#308)). ***An internal node*** in a tree is any node that has at least one child. That is, it is any node that is not a leaf. A ***complete binary tree*** is a binary tree that satisfies the following conditions: - All internal nodes have two children. - All leaves have depth *d.* An ***essentially complete binary tree*** is a binary tree that satisfies the following conditions: - It is a complete binary tree down to a. depth of *d*–1. - The nodes with depth *d* are as far to the left as possible. Although essentially complete binary trees are difficult to define, it is straightforward to grasp their properties from a picture. [Figure 7.4](#ch07fig04) shows an essentially complete binary tree. [](fig7-4_0.jpg) Figure 7.4: An essentially complete binary tree. We can now define a heap. A *heap* is an essentially complete binary tree such that - The values stored at the nodes come from an ordered set. - The value stored at each node is greater than or equal to the values stored at its children. This is called the heap property. [Figure 7.5](#ch07fig05)shows a heap. Because we are presently interested in sorting, we will refer to the items stored in the heap as *keys.* [](fig7-5_0.jpg) Figure 7.5: A heap. Suppose that somehow we have arranged the keys that are to be sorted in a heap. If we repeatedly remove the key stored at the root while maintaining the heap property, the keys will be removed in nonincreasing sequence. If, while removing them, we place them in an array starting with the *n*th slot and going down to the first slot, they will be sorted in nondecreasing sequence tn the array. After removing the key at the root, we can restore the heap property by replacing the key at the root with the key stored at the bottom node (by "bottom node" we mean the far-right leaf), deleting the bottom node, and calling a procedure *siftdown* that "sifts" the key now at the root down the heap until the heap property is restored. The sifting is accomplished by initially comparing the key at the root with the larger of the keys at the children of the root. If the key at the root is smaller, the keys are exchanged. This process is repeated down the tree until the key at a node is not smaller than the larger of the keys at its children. [Figure 7.6](#ch07fig06) illustrates this procedure. High-level pseudocode for it is as follows: ``` void siftdown (heap& H) // H starts out having the { // heap property for all node parent, largerchild; // nodes except the root. // H ends up a heap. parent = root of H; largerchild = parent's child containing larger key; while (key at parent is smaller than key at largerchild){ exchange key at parent and key at largerchild; parent = largerchild; largerchild = parent's child containing larger key; } } ``` [](fig7-6_0.jpg) Figure 7.6: Procedure *siftdown* sifts 6 down until the heap property is restored. High-level pseudocode for a function that removes the key at the root and restores the heap property is as follows: ``` keytype root (heap& H) { keytype keyout; keyout = key at the root; move the key at th bottom node to the root; // Bottom node is, delete the bottom node; // far-right leaf. siftdown (H); // Restore the return keyout; // heap property. } ``` Given a heap of *n* keys, the following is high-level pseudocode for a procedure that places the keys in sorted sequence into an array *S.* ``` void removekeys (int n, heap H, keytype S[]) { index i; for (i = n; i >= 1; i--) S[i] = root (H); } ``` The only task remaining is to arrange the keys in a heap in the first place. Let's assume that they have been arranged in an essentially complete binary tree that does not necessarily have the heap property (we will see how to do this in the next subsection). We can transform the tree into a heap by repeatedly calling *siftdown* to perform the following operations: First, transform all subtrees whose roots have depth *d*–1 into heaps; second, transform all subtrees whose roots have depth *d* – 2 into heaps; … finally, transform the entire tree (the only subtree whose root has depth 0) into a heap. This process is illustrated in [Figure 7.7](#ch07fig07) and is implemented by the procedure outlined in the following high-level pseudocode. ``` void makeheap (int n, heap& H) // H ends-up a heap. { index i; heap Hsub; // Hsub ends up a heap. for (i = d - 1; i >= 0; i--) // Tree has depth d. for (all subtrees Hsub whose roots have depth i) siftdown (Hsub); } ``` [](fig7-7_0.jpg) Figure 7.7: Using *siftdown* to make a heap from an essentially complete binary tree. After the steps shown, the right subtree, whose root has depth *d* — 2, must be made into a heap, and finally the entire tree must be made into a heap. Finally, we present high-level pseudocode for Heapsort (it is assumed that the keys are already arranged in an essentially complete binary tree in *H*): ``` void heapsort (int n, heap H, // H ends up a heap. keytype S[]) { makeheap (n, H); removekeys (n, H, S); } ``` It may seem that we were not telling the truth earlier because this Heapsort algorithm does not appear to be an in-place sort. That is, we need extra space for the heap. However, next we implement a heap using an array. We show that the same array that stores the input (the keys to be sorted) can be used to implement the heap, and that we never simultaneously need the same array slot for more than one purpose.