Binary Heap - Data Structure

1. The (binary) heap data structure is an array object that we can view as a nearly complete binary tree




2. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.




3. An array A that represents a heap is an object with two attributes: A.length, which gives the number of elements in the array, and A.heap-size, which represents how many elements in the heap are stored within array A.




4. Although A[1 ... A.length] may contain numbers, only the elements in A[1 .. A.heap-size], where 0 ≤ A.heap-size ≤ A.length, are valid elements of the heap.




5. The root of the tree is A[1], and given the index i of a node, we can easily compute the indices of its parent, left child, and right child




1. Parent index: floor(i/2) i.e. 3/2 = 1 and not 2.




2. Left node index: 2i




3. Right node index: 2i + 1




6. There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property:




1. Max heap: A[PARENT(i)] ≥ A[i] ; for every node other than root. Thus, the largest element in a max-heap is stored at the root




2. Min heap: A[PARENT(i)] ≤ A[i] ; The smallest element in a min-heap is at the root.




7. For the heapsort algorithm, we use max-heaps. Min-heaps commonly implement priority queues

Properties of a Heap

1. Height of a node in a heap is the number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root.




2. Since a heap of n elements is based on a complete binary tree, its height is Θ(lg n).



3. The basic operations on heaps run in time at most proportional to the height of the tree and thus take O(lg n) time.

Solved Examples on Heaps.

Q. What are the minimum and maximum numbers of elements in a heap of height h?

1. At least 2^h and at most 2^h+1 - 1 Can be seen because a complete binary tree of depth h - 1 has 2^h - 1 elements, and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h - 1 exclusive and the number in a complete binary tree of depth h inclusive.

Ans . At least 2^h and at most 2^h+1 - 1

Q. Show that an n-element heap has height ⌊ lg n ⌋.

1. Write n = 2^m - 1 + k where m is as large as possible. Then the heap consists of a complete binary tree of height m - 1, along with k additional leaves along the bottom. The height of the root is the length of the longest simple path to one of these k leaves, which must have length m. It is clear from the way we defined m that m = ⌊ lg n ⌋

Q. Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.

1. If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree. So, it is larger than it's parent, so, the heap property is violated at the parent of the maximum element in the subtree

Q. Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

1. The smallest element must be a a leaf node. Suppose that node x contains the smallest element and x is not a leaf. Let y denote a child node of x. By the max-heap property, the value of x is greater than or equal to the value of y. Since the elements of the heap are distinct, the inequality is strict. This contradicts the assumption that x contains the smallest element in the heap.

Q. Is an array that is in sorted order a min-heap?

1. Yes, it is. The index of a child is always greater than the index of the parent, so the heap property is satisfied at each vertex.

Q. Is the array with values {23; 17; 14; 6; 13; 10; 1; 5; 7; 12} a max-heap?

1. No, the array is not a max-heap. 7 is contained in position 9 of the array, so its parent must be in position 4, which contains 6. This violates the max-heap property.

Q. Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by ⌊ n/2 ⌋ + 1, ⌊ n/2 ⌋ + 2, ..., n.

1. It suffices to show that the elements with no children are exactly indexed by {⌊ n/2 ⌋ + 1, ... ,n}. Suppose that we had an i in this range. It's children would be located at 2i and 2i + 1 but both of these are ≥ 2⌊ n/2 ⌋+ 2 > n and so are not in the array. Now, suppose we had an element with no kids, this means that 2i and 2i + 1 are both > n, however, this means that i > n/2.




2. This means that i ∈ {⌊ n/2 ⌋ + 1, ... ,n}.

Previous

Next