Max-Heap

gistfile1.c

#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

int heapSize = 0;

int leftChild(int index)
{
  return 2 * index;
}

int rightChild(int index)
{
  return 2 * index + 1;
}

int parent(int index)
{
  return floor(index/2);
}

void heapify(int h[], int index)
{
  int largest;
  int l = leftChild(index);
  int r = rightChild(index);

  if(l <= heapSize && h[l] > h[index])
    largest = l;
  else
    largest = index;

  if(r <= heapSize && h[r] > h[largest])
    largest = r;

  if(largest != index){
    swap(h[index], h[largest]);
    heapify(h, largest);
  }
  
}
void buildMaxHeap(int h[])
{
  for(int i = floor(heapSize/2); i > 0; i--){
    heapify(h, i);
  }
}

void increaseKey(int h[], int index, int key)
{
  h[index] = key;
  while(index > 1 && h[parent(index)] < h[index]){
    swap(h[index], h[parent(index)]);
    index = parent(index);
  }
}

void decreaseKey(int h[], int index, int key)
{
  int child, temp;
  for(temp = h[index]; leftChild(index) < key; index = child){
    child = leftChild(index);
    if((child != key - 1) && (h[child] < h[child+1]))
      child++;

    if(temp < h[child])
      h[index] = h[child];
    else;
      break;
  }

  h[index] = temp;
}

void insertElement(int h[], int key)
{
  ++heapSize;
  h[heapSize] = NULL;
  increaseKey(h,heapSize,key);
}

int deleteMax(int h[])
{
  int max = h[1];
  h[1] = h[heapSize];
  --heapSize;
  heapify(h,1);
  return max;
}

int deleteMin(int h[])
{

  return 0;
}

int remove(int h[], int key)
{
  --heapSize;
  h[1] = h[heapSize];
  decreaseKey(h, 1, key);
  
}

int main()
{
  int heap[100];

  heap[0] = 400;
  heap[1] = 4;
  heap[2] = 1;
  heap[3] = 3;
  heap[4] = 2;
  heap[5] = 16;
  heap[6] = 9;
  heap[7] = 10;
  heap[8] = 14;
  heap[9] = 8;
  heap[10] = 7;
  
  heapSize = 10;

  for(int i = 1; i <= heapSize; i++){
    cout << heap[i] << " ";
  }
  cout << endl;

  heapify(heap, 2);

  for(int i = 1; i <= heapSize; i++){
    cout << heap[i] << " ";
  }
  cout << endl;

  buildMaxHeap(heap);

  cout << "Build Max Heap" << endl;
  for(int i = 1; i <= heapSize; i++){
    cout << heap[i] << " ";
  }
  cout << endl;
  
  insertElement(heap, 13);
  cout << "Insert element" << endl;
  for(int i = 1; i <= heapSize; i++){
    cout << heap[i] << " ";
  }
  cout << endl;
}

Assignment:

Write a program to maintain a binary heap. The data field of each node contains an integer. The operations should include:

Buildheap: (B) build a heap with an input of N items.
Insert: (I) insert an element in the heap.
Deletemin: (D) delete the minimum of the heap. (Remember: a minimum of a heap must be a leaf.)
Deletemax (DM) delete the maximum of the heap.
Decreasekey: (DK) decrease the value of the item at position p by a positive amount.
Increasekey (IK) increase the value of the item at position p by a positive amount.
Remove (R) remove the node at position p from the heap.

You should use an array to implement the heap. Initialize the array size as 100. You may use a variable to maintain the size of the current heap. You may assume that each data is less than 10000, and greater than 0. The sentinels must be used.
Your program should read an input file first. A simple example of input file is:

After each operation, you should print the heap.

B 23 76 19 230 7000 913
I 34
D
DK 3 32
IK 4 39
R 5
DM
..............................