Heap.cpp

// A C++ program to demonstrate common Binary Heap Operations 
#include<iostream> 
#include<climits> 
using namespace std;

struct heaps{
	int *vetor;
	int tamMax;
	int tamAtual;
}; 

void inicializaHeap(int cap, heaps* heap){
	heap->tamAtual = 0;
	heap->tamMax = cap;
	heap->vetor = new int[cap];	
}

int pai(int i){
	return (i-1)/2;
}

int filhoEsq(int i){
	return (2*i + 1);
} 


int filhoDir(int i){
	return (2*i + 2);
}

int getMin(heaps* heap){
	return heap->vetor[0];
} 

void troca(int *x, int *y) 
{ 
	int temp = *x; 
	*x = *y; 
	*y = temp; 
} 

void inserir(heaps* heap, int chave){
	if(heap->tamAtual == heap->tamMax){
		cout<<"\nTamanho maximo atingido, chave nao pode ser inserida\n";
		return;
	}
	
	heap->tamAtual++;
	int i = heap->tamAtual - 1;
	heap->vetor[i] = chave;
	
	while(i != 0 && heap->vetor[pai(i)] > heap->vetor[i]){
		troca(&heap->vetor[i], &heap->vetor[pai(i)]);
		i = pai(i);
	}
}

void decreaseKey(int i, int valor, heaps* heap){
	heap->vetor[i] = valor;
	while(i != 0 && heap->vetor[pai(i)] > heap->vetor[i]){
		troca(&heap->vetor[i], &heap->vetor[pai(i)]);
		i = pai(i);
	}
}

void minHeapify(int i, heaps* heap){
	int esq = filhoEsq(i);
	int dir = filhoDir(i);
	int menor = i;
	
	if(esq < heap->tamAtual && heap->vetor[esq] < heap->vetor[i])
		menor = i;
	if(dir < heap->tamAtual && heap->vetor[dir] < heap->vetor[menor])
		menor = dir;
	if(menor != i){
		troca(&heap->vetor[i], &heap->vetor[menor]);
		minHeapify(menor, heap);
	}
}

int extractMin(heaps* heap) 
{ 
	if(heap->tamAtual <= 0)
		return INT_MAX;
	if(heap->tamAtual == 1){
		heap->tamAtual --;
		return heap->vetor[0];
	}
	
	int raiz = heap->vetor[0];
	heap->vetor[0] = heap->vetor[heap->tamAtual-1];
	heap->tamAtual --;
	minHeapify(0, heap);
	
	return raiz;
}

void deletar(int i, heaps* heap){
	decreaseKey(i, INT_MIN, heap);
	extractMin(heap);
}


/* A class for Min Heap 
class MinHeap 
{ 
	int *harr; // pointer to array of elements in heap 
	int capacity; // maximum possible size of min heap 
	int heap_size; // Current number of elements in min heap 
public: 
	// Constructor 
	MinHeap(int capacity); 

	// to heapify a subtree with the root at given index 
	void MinHeapify(int ); 

	int parent(int i) { return (i-1)/2; } 

	// to get index of left child of node at index i 
	int left(int i) { return (2*i + 1); } 

	// to get index of right child of node at index i 
	int right(int i) { return (2*i + 2); } 

	// to extract the root which is the minimum element 
	int extractMin(); 

	// Decreases key value of key at index i to new_val 
	void decreaseKey(int i, int new_val); 

	// Returns the minimum key (key at root) from min heap 
	int getMin() { return harr[0]; } 

	// Deletes a key stored at index i 
	void deleteKey(int i); 

	// Inserts a new key 'k' 
	void insertKey(int k); 
}; 

// Constructor: Builds a heap from a given array a[] of given size 
MinHeap::MinHeap(int cap) 
{ 
	heap_size = 0; 
	capacity = cap; 
	harr = new int[cap]; 
} 

// Inserts a new key 'k' 
void MinHeap::insertKey(int k) 
{ 
	if (heap_size == capacity) 
	{ 
		cout << "\nOverflow: Could not insertKey\n"; 
		return; 
	} 

	// First insert the new key at the end 
	heap_size++; 
	int i = heap_size - 1; 
	harr[i] = k; 

	// Fix the min heap property if it is violated 
	while (i != 0 && harr[parent(i)] > harr[i]) 
	{ 
	swap(&harr[i], &harr[parent(i)]); 
	i = parent(i); 
	} 
} 

// Decreases value of key at index 'i' to new_val. It is assumed that 
// new_val is smaller than harr[i]. 
void MinHeap::decreaseKey(int i, int new_val) 
{ 
	harr[i] = new_val; 
	while (i != 0 && harr[parent(i)] > harr[i]) 
	{ 
	swap(&harr[i], &harr[parent(i)]); 
	i = parent(i); 
	} 
} 

// Method to remove minimum element (or root) from min heap 
int MinHeap::extractMin() 
{ 
	if (heap_size <= 0) 
		return INT_MAX; 
	if (heap_size == 1) 
	{ 
		heap_size--; 
		return harr[0]; 
	} 

	// Store the minimum value, and remove it from heap 
	int root = harr[0]; 
	harr[0] = harr[heap_size-1]; 
	heap_size--; 
	MinHeapify(0); 

	return root; 
} 


// This function deletes key at index i. It first reduced value to minus 
// infinite, then calls extractMin() 
void MinHeap::deleteKey(int i) 
{ 
	decreaseKey(i, INT_MIN); 
	extractMin(); 
} 

// A recursive method to heapify a subtree with the root at given index 
// This method assumes that the subtrees are already heapified 
void MinHeap::MinHeapify(int i) 
{ 
	int l = left(i); 
	int r = right(i); 
	int smallest = i; 
	if (l < heap_size && harr[l] < harr[i]) 
		smallest = l; 
	if (r < heap_size && harr[r] < harr[smallest]) 
		smallest = r; 
	if (smallest != i) 
	{ 
		swap(&harr[i], &harr[smallest]); 
		MinHeapify(smallest); 
	} 
} 

// A utility function to swap two elements 
void swap(int *x, int *y) 
{ 
	int temp = *x; 
	*x = *y; 
	*y = temp; 
} 

// Driver program to test above functions 
int main() 
{ 
	MinHeap h(11); 
	h.insertKey(3); 
	h.insertKey(2); 
	h.deleteKey(1); 
	h.insertKey(15); 
	h.insertKey(5); 
	h.insertKey(4); 
	h.insertKey(45); 
	cout << h.extractMin() << " "; 
	cout << h.getMin() << " "; 
	h.decreaseKey(2, 1); 
	cout << h.getMin(); 
	return 0; 
}*/

int main(void){
	heaps *h;
	inicializaHeap(11, h);
	inserir(h, 3);
	inserir(h, 2);
	inserir(h, 1);
	inserir(h, 15);
	inserir(h, 5);
	inserir(h, 4);
	inserir(h, 45);
	
	for(int i=0; i<11; i++){
		cout<<h->vetor[i]<<" ";
	}
}