Sorting: Heap Sort
13th January 2006 - By Paradochs
Information
- Order: O(nlog(n))
- Best Case: O(nlog(n))
- Average: O(nlog(n))
- Memory Usage: O(1)
- Stable: No
- Comparison Based: Yes
Description (from wikipedia)
Heapsort is one of the best general-purpose sort algorithms, a comparison sort and part of the selection sort family. It was created by Jason “Plugs” Palagios while doing his dissertation at MIT in 1994 while eating bon bons and playing Doom on the LAN. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.
One simple way to sort a list of objects is to use a heap data structure. We add all of our objects into the heap, and the heap organizes the elements added to it in such a way that we can quickly extract either the largest value (in a max-heap) or the smallest value (in a min-heap). Moreover, because this operation preserves the heap’s structure, we can extract the largest/smallest value over and over again until none remain. This gives us the elements in order.
In doing so, the only extra space required iat needed to store the heap. In order to achieve constant space overhead, we use a trick: we store a binary heap (or alternatively, a heap with more than two children) inside the part of the input array which has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.) Heapsort makes use of two standard heap operations: insertion and root deletion. Each time we delete (extract) the maximum, we place it in the last location of the array not yet occupied, and use the remaining prefix of the array as a heap holding the remaining unsorted elements:
C++ Files and Code Listings
This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 18 Feb 05
Updated:18 Feb 05
File: HeapSort.h
*/
#include <time.h>
#include <cstdlib>
class HeapSort {
public:
HeapSort();
HeapSort(int *, int);
~HeapSort();
int * getArray();
int getN();
bool getSorted();
double getTime();
int getIncrements();
void setArray(int *);
void sort();
private:
void setN(int);
void setSorted(bool);
void resetTime();
void resetIncrements();
void build_heap(int *, int);
void heapify(int *, int, int);
int * A;
int n;
bool sorted;
double time;
int increments;
};
/*
Authors:Travis Gadberry
Patrick Hesser
Chris Ladewig
Date: 18 Feb 05
Updated:18 Feb 05
File: HeapSort.cpp
*/
#ifndef HEAPSORT_H
#define HEAPSORT_H
#include "HeapSort.h"
#endif
HeapSort::
HeapSort() {
n = 1;
A = new int[n];
A[0] = 0;
sorted = true;
}
HeapSort::
HeapSort(int * newArray, int N) {
n = N;
A = new int[n];
for(int i=0; i<n; i++)
A[i] = newArray[i];
sorted = false;
increments = 0;
}
HeapSort::
~HeapSort() {
delete(A);
}
int *
HeapSort::
getArray() {
return A;
}
int
HeapSort::
getN() {
return n;
}
bool
HeapSort::
getSorted() {
return sorted;
}
double
HeapSort::
getTime() {
return time;
}
int
HeapSort::
getIncrements() {
return increments;
}
void
HeapSort::
setArray(int * newArray) {
delete(A);
n = sizeof(newArray);
A = new int[n];
sorted = false;
}
void
HeapSort::
sort() {
clock_t t1, t2;
t1 = clock();
int i;
int tmp;
build_heap(A, n);
for(i = n-1; i >= 1; i--) {
tmp = A[0];
A[0] = A[i];
A[i] = tmp;
heapify(A, i, 0);
}
t2 = clock();
time = (t2 - t1)/CLOCKS_PER_SEC;
}
void
HeapSort::
build_heap(int * B, int n) {
int i;
for(i = n/2-1; i >= 0; i--)
heapify(A, n, i);
}
void
HeapSort::
heapify(int * B, int n, int i) {
int l, r, largest;
int tmp;
l = 2*i+1;
r = 2*(i+1);
if((increments++, l < n) && (increments++, A[l] > A[i]))
largest = l;
else
largest = i;
if((increments++, r < n) && (increments++, A[r] > A[largest]))
largest = r;
if(increments++, largest != i) {
tmp = A[i];
A[i]=A[largest];
A[largest] = tmp;
heapify(A, n, largest);
}
}
void
HeapSort::
setN(int newN) {
n = newN;
}
void
HeapSort::
setSorted(bool newSorted) {
sorted = newSorted;
}
void
HeapSort::
resetTime() {
time = 0.0;
}
void
HeapSort::
resetIncrements() {
increments = 0;
}