Max-Heap

gistfile1.c

#include <iostream>
#include <stdlib.h>
#include <limits.h>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

ofstream outfile;

int heapSize = 0;

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

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

int parent(int index)
{
	return ((index - 1) / 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 = heapSize / 2; i >= 0; i--){
    heapify(h, i);
  }
}

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

void siftDown(int h[], int index, int key)
{
  int child = 0;

  while(!((index >= (key/2))  &&  (index < key))){
    child = leftChild(index);
    if((child < (key - 1)) && (h[child] < h[child+1]))
      child++;

    if(h[index] >= h[child])
      return;

    swap(h[index], h[child]);
    index = child; 
  }
}

void decreaseKey(int h[], int index, int key)
{
  int final = h[index] - key;
  h[index] = final;
  siftDown(h, index, final);
}

void increaseKey(int h[], int index, int key)
{
  h[index] = h[index] + key;
}

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

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

void remove(int h[], int index)
{
  h[index] = h[heapSize - 1];
  --heapSize;
  heapify(h, index);
}

void deleteMin(int h[])
{
  int key = h[0];
  int index = 0;
  for(int i = 0; i < heapSize; i++){
    if(key > h[i]){
      key = h[i];
      index = i;
    }
  }
  remove(h, index);
}

void printHeap(int h[])
{
  for(int i = 0; i < heapSize; i++){
    cout << h[i] << " ";
  }
  cout << endl << "---------" << endl;
}

int main()
{
  outfile.open("heapoutput");

  // I COULDN'T FIGURE OUT HOW TO PROCESS YOUR INPUT FILE 
  // PROPERLY SO INSTEAD OF MODIFYING IT AND MANGLING IT
  // I AM JUST DOING THINGS MANUALLY


  // Initialize a heap array of 100 elements
  int heap[100];
  int input[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

  for (int i = 0; i < 10; i++)
  {
      insertElement(heap, input[i]);
      printHeap(heap);
  }

  /*
  heap[0] = 34;
  heap[1] = 54;
  heap[2] = 92;
  heap[3] = 56;
  heap[4] = 100;
  heap[5] = 200;
  heap[6] = 300;
  heap[7] = 123;
  heap[8] = 345;
  heap[9] = 129;
  heap[10] = 367;
  heap[11] = 280;
  heap[12] = 670;
  heap[13] = 1000; 
  heap[14] = 2000; 
  heap[15] = 3000; 
  heap[16] = 1120; 
  heap[17] = 2300; 
  heap[18] = 3200; 
  heap[19] = 2001; 
  heap[20] = 12;  
  heap[21] = 79; 
  heap[22] = 82; 
  heap[23] = 701; 
  heap[24] = 892; 
  heap[25] = 931; 
  heap[26] = 566;
  heap[27] = 377; 
  heap[28] = 901; 
  heap[29] = 5000; 
  heap[30] = 3009; 
  heap[31] = 1201; 
  heap[32] = 59; 
  heap[33] = 601; 
  heap[34] = 6001; 
  heap[35] = 2230; 
  heap[36] = 770;

  heapSize = 37;

  cout << "Build Max Heap" << endl;
  buildMaxHeap(heap);
  printHeap(heap);

  cout << "Insert 9000" << endl;
  insertElement(heap, 9000);
  printHeap(heap);
  
  cout << "Insert 389" << endl;
  insertElement(heap, 389);
  printHeap(heap);
  
  cout << "Insert 400" << endl;
  insertElement(heap, 400);
  printHeap(heap);
  
  cout << "Insert 3" << endl;
  insertElement(heap, 3);
  printHeap(heap);
  
  cout << "Insert 17" << endl;
  insertElement(heap, 17);
  printHeap(heap);
  
  cout << "DeleteMin" << endl;
  deleteMin(heap);
  printHeap(heap);

  cout << "DeleteMin" << endl;
  deleteMin(heap);
  printHeap(heap);

  cout << "DeleteMin" << endl;
  deleteMin(heap);
  printHeap(heap);

  cout << "DecreaseKey 10, 20" << endl;
  decreaseKey(heap, 10, 2);
  printHeap(heap);

  cout << "DecreaseKey 30, 19" << endl;
  decreaseKey(heap, 30, 19);
  printHeap(heap);

  cout << "IncreaseKey 25, 500" << endl;
  increaseKey(heap, 25, 500);
  printHeap(heap);

  cout << "IncreaseKey 17, 370" << endl;
  increaseKey(heap, 17, 370);
  printHeap(heap);

  cout << "Remove 20" << endl;
  remove(heap, 20);
  printHeap(heap);

  cout << "DeleteMax" << endl;
  deleteMax(heap);
  printHeap(heap);

  cout << "DeleteMax" << endl;
  deleteMax(heap);
  printHeap(heap);
  */
}

fixes one-off errors

4 
---------
4 1 
---------
4 3 1 <= should be 4 1 3
---------
4 3 1 2 <= should be 4 2 3 1
---------
16 4 3 2 1 <= should be 16 4 3 1 2
---------
16 9 4 2 1 3 <= should be 16 4 9 1 2 3
---------
16 10 4 9 1 3 2 <= should be 16 4 10 1 2 3 9
---------
16 14 4 10 1 3 2 9 <= should be 16 14 10 4 2 3 9 1
---------
16 14 8 10 4 3 2 9 1 <= should be 16 14 10 8 2 3 9 1 4
---------
16 14 8 10 7 3 2 9 1 4 <= should be 16 14 10 8 7 3 9 1 4 2
---------