Data-Structures-Algorithms/Sorting/Heapsort.cpp at master · baamboohulk/Data-Structures-Algorithms · GitHub

History

131 lines (111 loc) · 3.33 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include <iostream>

#include <cstdio>

#include <vector>

#include <iostream>

#include <climits>

using namespace std; //Not the best tactic, used for cleaner code and better understanding

class Heap {

private:

std::vector<int> heap;

int hpsz;

public:

Heap(){

hpsz=0; //At first the Heap is Empty

heap.push_back(0); //Index 0 must be initialized because we start indexing from 1

}

Heap(std::vector<int>& array){

int n = array.size();

heap.push_back(100); //The first index of heap array is 1 so we must fill 0 index with dummy content let it be 0

heap.insert(heap.end(),array.begin(),array.end()); //προσθέτω το 0

hpsz=n; //Heap size = Heap Array size

for (int i = n / 2; i > 0; i--) combine(i);

}

void insert(int elmnt) {

heap.push_back(elmnt);

hpsz++;

int i = hpsz, parent = i / 2;

while ((i > 1) && (heap[parent] < heap[i]))

{

iter_swap(heap.begin() + parent, heap.begin() + i);

i = parent; parent = i / 2;

}

//Get max without deleting from heap

int peek_max(){

return heap[1];

}

void combine (int i){

int mp=i,left=2*i,right=(2*i)+1;

if((left<=hpsz) && (heap[left]>heap[mp])) {

mp = left;

}

if((right<=hpsz) && (heap[right]>heap[mp])) {

mp = right;

}

if(mp!=i) {

iter_swap(heap.begin() + i, heap.begin() + mp);

combine(mp);

}

int deletemax(){

if(isEmpty()) return -1;

int max = heap[1];

heap[1] = heap[hpsz--];

combine(1);

return max;

}

bool isEmpty(){

return (hpsz==0);

}

int getHeapSize(){

return (hpsz);

}

void heapSort(){

int temp = hpsz;

for (int i = hpsz; i > 1; i--) {

iter_swap(heap.begin() + 1, heap.begin() + i);

hpsz--;

combine(1);

}

hpsz = temp;

}

void printHeap(){

for (int i = 1; i <= hpsz; i++) {

printf("%d ", heap[i] );

}

printf("\n");

}

};

int main(){

Heap can be constructed using vector as input

int a[] = {3,4,10,8,15,16,17,12,11,20};

vector<int> heapin (a, a + sizeof(a) / sizeof(a[0]) ); //C++2003

//std::vector<int> heapin ({3,4,10,8,15,16,17,12,11,20}); //C++2011

// std::vector<int> heapin(std::begin(a), std::end(a)); //C++2003

Heap test(heapin);

Heap can be constructed using one by one insertion of elements

<-------------------------------------------------------------->

Heap test;

int num_elements;

printf("Enter number of elements\n");

scanf("%d\n",&num_elements);

int elem;

while(num_elements!=0) {

num_elements--;

scanf("%dendl",&elem );

test.insert(elem);

}

test.printHeap(); //Heap array

test.heapSort(); //after heap sorting the array does not include a list

test.printHeap(); //Sorted array

* Use the following loop to extract all the elements from head of max heap

while (!test.isEmpty()) {

printf("Max after delete: %d\n", test.deletemax());

}

Data-Structures-Algorithms/Sorting/Heapsort.cpp at master · baamboohulk/Data-Structures-Algorithms · GitHub

Expand file tree

Breadcrumbs

Heapsort.cpp

Latest commit

History

Breadcrumbs

Heapsort.cpp

File metadata and controls