Skip to content

Instantly share code, notes, and snippets.

@ckalbas
Created February 25, 2018 18:17
Show Gist options
  • Save ckalbas/fa993a0bcfb4fe7271ef67c4e50a9a57 to your computer and use it in GitHub Desktop.
Save ckalbas/fa993a0bcfb4fe7271ef67c4e50a9a57 to your computer and use it in GitHub Desktop.
Heapsort algorithm using recursive and loop solutions in C++
#include <stdio.h>
#include <iostream>
#define LENGTH 10
int heapSize = 0;
using namespace std;
void Exchange(int* A, int a, int b)
{
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
void MaxHeapify(int* A, int i)
{
while (i <= heapSize) {
int left = i*2;
int right = left+1;
int largest = 0;
if (left <= heapSize && A[left] > A[i])
{
largest = left;
}
else {
largest = i;
}
if (right <= heapSize && A[right] > A[largest]){
largest = right;
}
if (largest != i) {
Exchange(A, largest, i);
i = largest;
}else {
break;
}
}
}
void BuildMaxHeap(int* A)
{
heapSize = LENGTH-1;
for (int i = heapSize/2; i >= 0; i--)
{
MaxHeapify(A, i);
}
}
void HeapSort(int* A)
{
BuildMaxHeap(A);
for (int i = LENGTH -1; i > 0; i--)
{
Exchange(A, i, 0);
heapSize--;
MaxHeapify(A, 0);
}
}
int main() {
int test[LENGTH] = {1, 20, 13, 7, 9, 8, 5, 11, 2, 3};
HeapSort(test);
for (int i = 0; i <= LENGTH -1; i++)
{
cout << test[i] << ' ';
}
return 0;
}
#include <stdio.h>
#include <iostream>
#define LENGTH 10
int heapSize = 0;
using namespace std;
void Exchange(int* A, int a, int b)
{
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
void MaxHeapify(int* A, int i)
{
int left = i*2;
int right = left+1;
int largest = 0;
if (left <= heapSize && A[left] > A[i]) {
largest = left;
} else {
largest = i;
}
if (right <= heapSize && A[right] > A[largest]) {
largest = right;
}
if (largest != i) {
Exchange(A, largest, i);
MaxHeapify(A, largest);
}
}
void BuildMaxHeap(int* A)
{
heapSize = LENGTH-1;
for (int i = heapSize/2; i >= 0; i--)
{
MaxHeapify(A, i);
}
}
void HeapSort(int* A)
{
BuildMaxHeap(A);
for (int i = LENGTH -1; i > 0; i--)
{
Exchange(A, i, 0);
heapSize--;
MaxHeapify(A, 0);
}
}
int main() {
int test[LENGTH] = {1, 20, 13, 7, 9, 8, 5, 11, 2, 3};
HeapSort(test);
for (int i = 0; i <= LENGTH -1; i++)
{
cout << test[i] << ' ';
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment