Skip to content

Instantly share code, notes, and snippets.

@zerokarmaleft
Forked from buddylindsey/gist:1410596
Created November 30, 2011 20:31
Show Gist options
  • Save zerokarmaleft/1410689 to your computer and use it in GitHub Desktop.
Save zerokarmaleft/1410689 to your computer and use it in GitHub Desktop.
Max-Heap
#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);
*/
}
@zerokarmaleft
Copy link
Author

fixes one-off errors

@zerokarmaleft
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment