Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
* heap_sort.cpp (with array)
* Defines the entry point for the console application.
*/
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
//------------------------------------------
void max_heapify(int*arr,int n,int i)
{
int left_child = 2 * i + 1;
int right_child = 2 * i + 2;
int large = i;
if (left_child < n && arr[large] < arr[left_child])
{
large = left_child;
}
if (right_child < n && arr[large] < arr[right_child])
{
large = right_child;
}
if (large != i)
{
int temp;
temp = arr[i];
arr[i] = arr[large];
arr[large] = temp;
max_heapify(arr, n, large);
}
}
//
void make_max_heap(int* arr, int n)
{
for (int i = n / 2 + 1; i >= 0; i--)
{
max_heapify(arr, n, i);
}
}
//Heap Sort
void heap_sort(int* arr, int n)
{
make_max_heap(arr, n);
int temp;
for (int i = n-1 ; i > 0; i--)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
max_heapify(arr, i, 0);
}
}
//main
int main( )
{
int *a = new int[6];
a[0] = 8;
a[1] = 7;
a[2] = 9;
a[3] = 2;
a[4] = 5;
a[5] = -1;
heap_sort(a, 6);
for (int i = 0; i < 6; i++)
{
cout << a[i] << " ,";
}
cout << endl;
return 0;
}
/* test input and output
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.