Back to Code List
c++

Heap

A heap implementation via tree. Includes insert and deleteMin functions.

   main.cpp

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

const int ARRAY_SIZE = 50;// defined as a global constant for simplicity
ofstream outputFile;//defined as a global variable

class Heap
{
	private:
		int array_size;// the size of the array, index from 0 to array_size-1
		int heap_size;// elements of the heap are in H[1...heap_size]
		int * H;
		int left(int i) { return i * 2; } //the index of the left child of node i
		int right(int i) { return 2 * i + 1; } //the index of the right child of node i
		int parent(int i) { return i / 2; }//the index of the parent of node i
		void percolateDown(int);

	public:
		Heap(int * A, int num);
		Heap(int array_size_input = 5);
		~Heap() { delete [] H; };
		int deleteMin();
		void insert(int);
		void printHeap();
		void buildHeap();
		void heapSort();
};

//sort all elements of the heap and still use H to store the sorted list in descending order
void Heap::heapSort()
{
	int n = heap_size;
	for (int i = heap_size; i > 0; i --)
		H[i] = deleteMin();

	cout << endl;
	outputFile << endl;
	cout << "The following are the keys in the heap sorted in descending order: " << endl;
	outputFile << "The following are the keys in the heap sorted in descending order: " << endl;

	for (int i = 1; i <= n; i++)
	{
		cout << H[i] << " ";
		outputFile << H[i] << " ";
	}

	cout << endl;
	outputFile << endl;
}

//return and remove the smallest element from the heap 
int Heap::deleteMin()
{
	if (heap_size == 0) return 0;
	int min = H[1];
	H[1] = H[heap_size--];
	percolateDown(1);
	return min;
}

//build the heap for the elements in H[1...heap_size] and you can make
//use of the procedure percolateDown(int i), as discussed in class
void Heap::buildHeap()
{
	for (int i = heap_size / 2; i > 0; i--)
		percolateDown(i);
}

//percolate down from H[i]
void Heap::percolateDown(int i)
{
	int child;
	auto temp = H[i];
	for (; i * 2 <= heap_size; i = child) {
		child = i * 2;
		if (child != heap_size && H[child + 1] < H[child])
			child++;
		if (H[child] < temp)
			H[i] = H[child];
		else
			break;
	}
	H[i] = temp;
}

//insert a new key x into the heap H
void Heap::insert(int x)
{
	int hole = ++heap_size;
	for (; hole > 1 && x < H[hole / 2]; hole /= 2)
		H[hole] = H[hole / 2];
	H[hole] = x;
}

//A is an array, num is the number of elements in A
Heap::Heap(int *A, int num)
{
	array_size = ARRAY_SIZE;
	H = new int [array_size];
	for (int i = 1; i <= num; i++)
		H[i] = A[i-1];

	heap_size = num;
	buildHeap();
}

void Heap::printHeap()
{
	cout << endl;
	outputFile << endl;
	cout << "The following are the keys in the heap:" << endl;
	outputFile << "The following are the keys in the heap:" << endl;
	for (int i = 1; i <= heap_size; i++)
	{
		cout << H[i] << " ";
		outputFile  << H[i] << " ";
	}
	cout << endl;
	outputFile << endl;
}

int main()
{
	int A[10] = {24, 13, 18, 31, 65, 26, 19, 68, 21, 37};

	//build a heap using the elements of array A
	Heap heap(A, 10);

	//open files
	ifstream inputFile;
	inputFile.open("input.txt");
	if (!inputFile)
		cout << "Error opening the input file " << endl;
	
	//outputFile has been defined as a global variable
	outputFile.open("output.txt");
	if (!outputFile)
		cout << "Error opening the output file " << endl;

	string op;
	//read operations from the input file
	int x;
	while(inputFile >> op)
	{
		if (op == "insert")
		{
			inputFile >> x; // read the value x for insert
			heap.insert(x);
		}
		if (op == "deleteMin")
		{
			int temp = heap.deleteMin();
			cout << temp << endl;
			outputFile << temp << endl;
		}
	}

	//print the heap
	heap.printHeap();

	//sort all keys in the heap in descending order and print the sorted list 
	heap.heapSort();

	inputFile.close();
	outputFile.close();

	return 1;
}
    

   input.txt

deleteMin
insert 137 
insert 136 
insert 103 
insert 192 
deleteMin
insert 168 
insert 60 
insert 41 
insert 181 
insert 70 
deleteMin
deleteMin
deleteMin
insert 75 
insert 187 
insert 47 
insert 148 
insert 166 
insert 74 
insert 6 
deleteMin
insert 58
insert 174 
insert 12 
insert 91 
deleteMin
deleteMin
deleteMin
deleteMin
insert 92 
insert 30 
insert 182 
insert 78 
insert 4 
insert 80 
insert 146 
insert 18 
insert 14
deleteMin
    

   output.txt

13
18
19
21
24
6
12
26
31
37
4

The following are the keys in the heap:
14 41 18 68 47 60 30 174 70 74 58 78 80 65 75 187 181 148 166 137 92 136 182 103 91 168 146 192 

The following are the keys in the heap sorted in descending order: 
192 187 182 181 174 168 166 148 146 137 136 103 92 91 80 78 75 74 70 68 65 60 58 47 41 30 18 14