/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 */


#ifndef HEAPSORT_H
#define HEAPSORT_H

#include <stddef.h>
#include "assert.H"

template <class Iterator>
void heapSort(Iterator first, Iterator last);

template <class Iterator, class T>
void popHeap(Iterator first, Iterator last, T value, T& result);
/*
{
    size_t len = last - first;
    size_t holeIndex = 0;
    size_t secondChild = 2;

    result = *first;

    while (secondChild < len) {
	if (*(first + (secondChild - 1)) - *(first + secondChild) > 0)
	    secondChild--;
	*(first + holeIndex) = *(first + secondChild);
	holeIndex = secondChild;
	secondChild = 2 * (secondChild + 1);
    }
    
    if (secondChild == len) {
	*(first + holeIndex) = *(first + (secondChild - 1));
	holeIndex = secondChild - 1;
    }

    while (holeIndex != 0 && value - *(first + (holeIndex - 1)/2) > 0) {
	*(first + holeIndex) = *(first + (holeIndex - 1)/2);
	holeIndex = (holeIndex - 1)/2;
    }
    *(first + holeIndex) = value;
}
*/

template <class Iterator, class T>
T accumulateHeap(Iterator first, Iterator last, T value);

template <class Iterator>
void sortHeap(Iterator first, Iterator last);

template <class Iterator>
void partialHeapSort(Iterator first, Iterator cut, Iterator last);

template <class Iterator>
void makeHeap(Iterator first, Iterator last);

template <class Iterator, class T>
void adjustHeap(Iterator first, size_t parent, size_t len, T value);
/*
{
    size_t secondChild = 2 * (parent + 1);
    
    while (secondChild < len) {
	if (*(first + (secondChild - 1)) - *(first + secondChild) > 0)
	    secondChild--;
	if (value - *(first + secondChild) > 0) {
	    *(first + parent) = value;
	    return;
	}
	*(first + parent) = *(first + secondChild);
	parent = secondChild;
	secondChild = 2 * (secondChild + 1);
    }
    
    if (secondChild-- == len) 
	if (value - *(first + secondChild) < 0) {
	    *(first + parent) = *(first + secondChild);
	    parent = secondChild;
	}

    *(first + parent) = value;
}
*/

template <class Iterator, class T>
void pushHeap(Iterator first, Iterator last, T value);

#endif