Notes for Monday, 6 April
COEN 251: Data Structures and Algorithms

Spring 1998

#include <iostream.h>
#include <math.h>

void heapsort(int A[], int length);
void buildheap(int A[], int length);
void heapify(int A[], int heaplength, int root);
void swap(int& x, int& y);

void main()
{
	int A[100],	// The array that holds the heap
	    length,     // The length of the heap
	    i = 0,	// A counter for input/output of list
	    input;	// Used for reading in the list
	
    // Get the list of numbers:                (takes O(n) time)
	cout << "Please enter your numbers.\n"
		<< "Indicate the end of the list with a negative number: ";
	while ( (i < 100) && (input >= 0))
	{
		cin >> input;
		A[i] = input;
		i++;
	} 
	length = i-1;	// Save the length of the list
	 
	// Sort the list		       (takes O(n lg n) time)
	heapsort(A, length);
	
	// Print the sorted list:	       (takes O(n) time)
	cout << endl << "Here's the list sorted:\n";
	for ( i = 0 ; i < length ; i++ )
		cout << A[i] << "  ";
}



void heapsort(int A[], int length)//	       (takes O(n lg n) time)
{
	int heapsize = length;
	
	buildheap(A, length);	//Take the unsorted list and make it a heap
	for (int i = length-1; i >=1; i--)
	{
		swap(A[0], A[i]);
		heapsize--;
		heapify(A, heapsize, 0);		
	}
}

void buildheap(int A[], int length)	//     (takes O(n) time)
{	
	for (int i = floor((length)/2); i >= 0 ; i--)
		heapify(A, length, i);
}

void heapify(int A[], int heapsize, int root) //(takes O(h) time,
					// h is the height of root
{
	int left = 2*root+1, 
		right = 2*root +2,
		largest;
	
	if ( (left < heapsize) && (A[left] > A[root]))
		largest = left;
	else 
		largest = root;
	
	if ( (right < heapsize) && (A[right] > A[largest]))
		largest = right;
		
	if (largest != root)
	{
		swap(A[root], A[largest]);
		heapify(A, heapsize, largest);
	}
}

void swap(int& x, int& y)
{
	int temp;
	
	temp = x;
	x = y;
	y = temp;
}