Skip to content

Instantly share code, notes, and snippets.

@divanibarbosa
Created June 8, 2019 23:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save divanibarbosa/bfadea11dd68f43f403abd820302c153 to your computer and use it in GitHub Desktop.
Save divanibarbosa/bfadea11dd68f43f403abd820302c153 to your computer and use it in GitHub Desktop.
HeapSort em C++ usando Classe
// HeapSort em C++ usando Classe
// Criado por: profa. Divani Barbosa Gavinier
// Curriculo Lattes: http://lattes.cnpq.br/8503400830635447
// divanibarbosa@gmail.com
#include <iostream>
using namespace std;
class Heap {
private: int *vHeap, tam_max, n;
public: Heap(int tam) {
tam_max = tam;
n = 0;
vHeap = new int[tam];
}
public: bool vazio() { return n==0; }
public: bool cheio() { return n==tam_max; }
public: bool insere(int v) {
if (cheio()) return false;
vHeap[n] = v;
MoveAcima(n); n++;
return true;
}
public: int remove() { // Elimina item com a chave máxima
int root = vHeap[0]; // (assume Heap não vazia)
vHeap[0] = vHeap[n-1];
n--;
MoveAbaixo(0);
return root;
}
public: void MoveAcima(int indice) {
int pai = (indice-1)/2;
int guarda = vHeap[indice];
while (indice > 0 && vHeap[pai] < guarda) {
vHeap[indice] = vHeap[pai];
indice = pai;
pai = (pai-1)/2;
}
vHeap[indice] = guarda;
}
public: void MoveAbaixo(int indice) {
int filhoMaior, filhoEsq, filhoDir;
int topo = vHeap[indice];
while (indice < n/2) { // enquanto No tiver pelo menos um filho
filhoEsq = 2*indice+1;
filhoDir = filhoEsq+1;
if (filhoDir < n && vHeap[filhoEsq] < vHeap[filhoDir])
filhoMaior = filhoDir;
else
filhoMaior = filhoEsq;
if (topo >= vHeap[filhoMaior]) break;
vHeap[indice] = vHeap[filhoMaior];
indice = filhoMaior;
}
vHeap[indice] = topo;
}
};
///////////////////////////////////////////////////////////////////
main() {
Heap h(20);
cout << " Inserindo itens: 90, 60, 80, 30, 55, 50, 70, 20, 10, 40, 5, 45\n";
h.insere(90); h.insere(60); h.insere(80);
h.insere(30); h.insere(55); h.insere(50); h.insere(70);
h.insere(20); h.insere(10); h.insere(40); h.insere(5);
h.insere(45);
cout << " Removendo itens: ";
while (!h.vazio()) cout << "[" << h.remove() << "] ";
cout << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment