Archive for the ‘HEAP’ Category

HEAP_TREE

March 27, 2008

HOME

/* PROGRAM TO IMPLEMENT HEAPTREE #include "iostream.h" #define SIZE 100 class heap { private: int a[SIZE]; void siftup(int i); void siftdown(int i); public: heap(); void build_heap(); void insert(int num); int deletemin(); void put_data(); int empty(); }; heap::heap() { int i; a[0] =0; // no. of elements in the heap for(i=1; i<SIZE; i++) a[i] = -1; } void heap::siftup(int i) { //i is the index of heap element to be sifted up int temp = a[i]; int p = i/2; //parent index while(temp1) { a[i] = a[p]; i =p; p= i/2; } a[i] = temp; } void swap(int &a,int &b) { int temp; temp =a; a = b; b = temp; } void heap::siftdown(int i) { int lchild = 2*i; int rchild = 2*i+1; while(a[rchild] != -1) { if(a[lchild] < a[i] && a[lchild] <= a[rchild]) { swap(a[lchild],a[i]); i = lchild; lchild = 2*i; rchild = 2*i+1; } else if(a[rchild] < a[i] && a[rchild] <a[lchild]) { swap(a[rchild],a[i]); i = rchild; lchild = 2*i; rchild = 2*i+1; } else break; } if(a[lchild] != -1 && a[lchild] < a[i]) swap(a[lchild],a[i]); } void heap::build_heap() { int n,i; cout<<endl<>n; a[0] = n; cout<<endl<<"enter the elements: "; //build complete binary tree for(i=1; i>a[i]; //heapify the binary tree for(i = n/2; i>=1; i--) siftdown(i); } void heap::insert(int num) { int n; n = ++a[0]; if(n > SIZE) { cout<<"memory limit exceeded. no insertion performed."; a[0]--; return; } a[n] = num; siftup(n); } int heap::deletemin() { int n,temp; if(a[0] == 0) { cout<<"empty heap. no deletion possible."; return -1; } temp = a[1]; n = a[0]--; a[1] = a[n]; siftdown(1); return temp; } void heap::put_data() { int i; cout<<endl; cout<<"the heap is: "; cout<<endl; for(i=1; i<=a[0]; i++) cout<<" "<<a[i]; } int heap::empty() { if(a[0] == 0) return 1; return 0; } void main() { int x; heap h; h.build_heap(); h.put_data(); cout<<endl<>x; h.insert(x); cout<<endl<<"after insertion: "; h.put_data(); cout<<endl<<endl<<"minimum element deleted: "; x = h.deletemin(); cout<<x<<endl; cout<<"after deletion: "; h.put_data(); } //PROGRAM ENDS /*OUTPUT: enter no. of elements in the heap: 9enter the elements: 18 2 13 10 15 3 7 16 8 the heap is: 2 8 3 10 15 13 7 16 18 enter the element to insert: 4 after insertion: the heap is: 2 4 3 10 8 13 7 16 18 15 minimum element deleted: 2 after deletion: the heap is: 3 4 7 10 8 13 15 16 18 Press any key to continue */

HOME

Advertisements