### 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:  

interpret it as a tree.


|
-----
|       |
- -

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  as root.
what do we do with  ?  --- 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 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 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 = arr[firstEmpty - 1] and bubble down that guy.

if(isEmpty()){
return -99999;          // ideally do a proper error throw handling
}

int root = arr;
arr = 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.


|
------
|          |
-- -
|
-

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