Created
June 8, 2019 23:14
-
-
Save divanibarbosa/bfadea11dd68f43f403abd820302c153 to your computer and use it in GitHub Desktop.
HeapSort em C++ usando Classe
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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