heap data structure

 
##################### 
####    heap     #### 
##################### 
 
- to be distinguished from "heap memory" "stack memory" which is a completely different topic. 
- a special tree where parent nodes are always bigger( or smaller) than child nodes. 
- no condition dictating the relations between left/right child nodes. 
- often the tree is binary, but not necessarily. lets assume it's binary heap unless otherwise specified. 
- so heap is a "partially" ordered/sorted structure. a bigger/smaller val can exist in the deeper depth. 
- used for heapsort, Dijkstra's algo, and other graph algo. 
- a good underlying structure for implementing a priority queue (= ADT). 
- biggest node at root = max heap 
- smallest node at root = min heap 
 
(ref) 
http://www.curiocube.com/mikata/hello/ch12_heapmore.php 
http://ppp-lab.sakura.ne.jp/ProgrammingPlacePlus/algorithm/data_struct/009.html 
http://en.wikipedia.org/wiki/Heap_(data_structure) 
 
 
NOTE: the process of building a heap structure is called "heapify" 
 
 
######################################## 
####   implementation with array    #### 
######################################## 
 
often heap is implemented using array. 
 
 
an array:  [0][1][2][3][4][6][7] 
 
interpret it as a tree. 
 
      [1] 
       | 
  [2]-----[3] 
   |       | 
[4]-[5] [6]-[7] 
 
 
take a node index as [N] 
left-child index is [2*N] 
right-child index is [2*N + 1] 
 
for the above to work, need to take [1] as root. 
what do we do with [0] ?  --- we usually use it to store the size of the heap. 
 
 
insert(input)  : add input to the array[lastElem + 1], and compare it to its parent node, and repeatedly bubble it up (official term is "sift up"). 
deleteMin()    : remove root, and put the array[lastElem] at array[1] and bubble down (called "sift down"). the reason we bring array[lastElem] to the root once is to maintain the array. 
 
 
 
#################################### 
####   computation complexity   #### 
#################################### 
 
worst case 
 
find[Max|Min]   :   O(1) 
delete[Max|Min] :   O(1) 
insert(x)       :   O(log n) 
 
 
as above, searching max/min is O(1) but note heap is NOT suitable for other kind of search, in fact generic search is usually not in scope of implementation. 
 
insert() is just put the val at the end, and bubble up the tree. the depth of the tree is log N. 
 
 
 
 
#################################### 
####   implementation in C++    #### 
#################################### 
 
lets say, min = root 
 
we dont use arr[0] for storing the size(= firstEmpty index) just for the sake of code readability. 
 
---------------------------------------  //  heap.h 
 
#include <iostream> 
using namespace std; 
 
template <typename T> class CHeap 

 public: 
 CHeap(): capacity(5), firstEmpty(1) { arr = new T[capacity]; } 
  void printHeap(); 
  bool isEmpty(); 
  void insert(T); 
  T deleteMin(); 
 private: 
  void resize(); 
  int capacity; 
  int firstEmpty; 
  T* arr; 
}; 
 
template <typename T> void CHeap<T>::printHeap() 

  for(int i = 1; i < firstEmpty; i++) 
    cout << arr[i] << " "; 
  cout << endl; 

 
template <typename T> bool CHeap<T>::isEmpty() 

  if(firstEmpty == 1) 
    return true; 
  else 
    return false; 

 
template <typename T> void CHeap<T>::insert(T t) 

  if(firstEmpty == capacity) 
    resize(); 
 
  arr[firstEmpty] = t;  // add the elem to the end of the array/tree 
  firstEmpty++; 
 
  int idx = firstEmpty-1; 
  while(true) // bubble the elem up the tree 
    { 
      if(idx == 1)  // reached root, then break 
        break; 
      if(arr[idx/2] > arr[idx])  // swap 
        { 
          arr[idx/2] = arr[idx/2] + arr[idx]; 
          arr[idx] = arr[idx/2] - arr[idx]; 
          arr[idx/2] = arr[idx/2] - arr[idx]; 
        } 
      idx = idx/2; 
    } 

 
template <typename T> void CHeap<T>::resize() 

 
  T* arr2 = new T[capacity * 2]; 
 
  for(int i = 0; i < capacity; i++) 
    arr2[i] = arr[i]; 
 
  delete [] arr; 
  arr = arr2; 
  capacity = capacity * 2; 

 
template <typename T> T CHeap<T>::deleteMin() 

  // essentially we pop the root, and promote the next min guy from either of left/right child nodes. 
  // but one trick is we need to take care of the last elem in the array. 
  // so we just do arr[1] = arr[firstEmpty - 1] and bubble down that guy. 
 
  if(isEmpty()){ 
    return -99999;          // ideally do a proper error throw handling 
      } 
 
  int root = arr[1]; 
  arr[1] = arr[firstEmpty - 1]; 
 
  int idx = 1; 
  int left; 
  int right; 
  int tmp; 
  while(true)      // bubble down loop 
    { 
      left = idx * 2; 
      right = left + 1; 
      tmp = 0; 
      if( left >= firstEmpty) // no child 
        break; 
      else if( right >= firstEmpty) // one child 
        tmp = left; 
      else if( arr[left] <= arr[right] ) // two children, left is smaller 
        tmp = left; 
      else // two children, right is smaller 
        tmp = right; 
      if( arr[idx] > arr[tmp]) 
        { 
          arr[tmp] = arr[tmp] + arr[idx]; 
          arr[idx] = arr[tmp] - arr[idx]; 
          arr[tmp] = arr[tmp] - arr[idx]; 
          idx = tmp; 
        } 
      else 
        break; 
    } 
 
  firstEmpty--; 
  return root; 

 
---------------------------------------------  //  main.cpp 
 
#include "heap.h" 
 
int main() 

  CHeap<int> ch; 
  ch.insert(12); 
  ch.insert(34); 
  ch.insert(56); 
  ch.insert(78); 
  ch.insert(90); 
  ch.insert(34); 
  ch.insert(56); 
  ch.insert(7); 
  ch.insert(88); 
 
  ch.printHeap(); //  7 12 34 34 90 56 56 78 88 
 
  while(!ch.isEmpty())                // this is heap sort 
    cout << ch.deleteMin() << " ";    // 7 12 34 34 56 56 78 88 90 
  cout << endl; 
 
  return 0; 

 
--------------------------------------------- 
 
 
====> visualizing the above example heap would be as below. 
 
           [7] 
            | 
      [12]------[34] 
       |          | 
   [34]--[90] [56]-[56] 
    | 
[78]-[88] 
 
 

  1. 2014-06-23 23:46:06 |
  2. Category : data_structure
  3. Page View:

Google Ads