Last active
July 13, 2020 22:28
-
-
Save divanibarbosa/58679cbb4f5e1e493a5211f7e8366659 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: void listagem() { | |
for(int i=0; i<n; i++) | |
cout << "vHeap[" << i << "] = " << vHeap[i] << endl; | |
} | |
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 << " Listagem: " << endl; | |
h.listagem(); | |
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