3.8.5 Heap

Knowledge Base > Algorithm > Data Structure

Overview

Heap is an array object that is usually seen as a nearly complete binary tree, whereas it satisfies the heap property, for every node other than the root node. The tree-represented heap is completely filled on all levels except the lowest, and is always filled from the left-most point[1]. We usually refer a heap to the binary heap, where a parent node can only contains at most two child nodes. There are two kinds of binary heap, max-heap and min-heap. A max heap is a heap that satisfies its max-heap property: for every node i other than the root, A[Parent(i)] ≥ A[i], that is, the value of a node is at most the value of its parent. Therefore, the largest element in a max-heap is stored at the root. Similarly, a min-heap operates in the other way: for every node i other than the root, A[Parent(i)] ≤ A[i]. Thus, the smallest element in a min-heap is stored at the root.

Basic Operation

• int length(heap A):
  return the number of elements in the array.
• int heap-size(heap A):
  return the number of elements in the heap stored within the array, where heap-size(A) <= length(A).
• int height(heap A):
  return the height of node x in the tree. This operations runs at O(h) time on a heap of height h.
• int parent(int i):
  return the index of parent of node at index i.
• int left(int i):
  return the index of left child of node at index i.
• int right(int i):
  return the index of right child of node at index i.
• void heapify(heap A, int i):
  For maintaining heap property, we assume the heap rooted at left(i) and right(i) maintain heap property, but element at i might be smaller than element at left(i) and right(i), which violates the heap property. So,heapify() let the value of A[i] flows down in the heap by recursively calling heapify() to fix up the relationships among A[i], A[left(i)] and A[right(i)], so that the heap at index i maintains. This operates runs at O(lg n).
• void build-heap(heap A):
  In order to maintain a heap, we need to perform heapify() on every internal node going through the remaining nodes of the tree, from the last internal node to the root, for an array ranged A[0…(n-1)]. Thus, the operation runs at an upper bound, ⋅ O(lg n) = O(n ⋅ lg n).

Algorithm

Pseudocode

Heapify(A,i)
 

1 l ← Left(i) 2 r ← Right(i) 3 if l ≤ heap-size[A] and A[l] > A[i] 4    then largest ← l 5    else largest ← i 6 if r ≤ heap-size[A] and A[r] > A[largest] 7    then largest ← r 8 if largest≠i 9    then swap A[i] ↔ A[largest] 10       Heapify(A,largest)

Build-Heap(A)

1 heap-size[A] ← length[A] 2 for i ←⌊length[A]∕2⌋downto 1 3 do Heapify(A,i)

Analysis

In the heapify() procedure, the worst case could be swapping every element from the root to the leaf node, for total counts of O(lg n) nodes. Next, we repeat the heapify() procedure from the mid array descending to the first element, and thus construct a O(n ⋅ lg n) of comparisons and swaps, in the worst case.

The intuitive upper bound for build-heap is O(n ⋅ lg n), however, a careful analysis shows the tighter upper bound as follow:
We know that the an n-element heap has height ⌈lg n⌉ (from property 3.8.4.5), and at most ⌈⌉ nodes at height level H (from property 3.8.4.6). Thus, calling heapify() method for each element from middle to root equals to calling for each element from middle height to root height. That is,

Source Code

Here is the heap implementation, written in C:

• Max Heap (C)
  
  
  

Related Topics

• Tree
• HeapSort