The GroupIndex Template Library

---

heap.h

#ifndef DEF_HEAP
#define DEF_HEAP
/* *******************************************************************************
   * TEMPLATES FUER HEAP-VERWALTUNG                                              *
   *******************************************************************************
*/

namespace groupindex
{
 
template<class ItemClass> 
void trickle(ItemClass** heap, int i, int m)
// Versickern von heap[i] bis max. heap[m]
{
        ItemClass* t;
        int j;

        while (2*i <= m) // so lange heap[i] linken Sohn hat
        {
                
                j = 2*i; // heap[j] ist linker Sohn von heap[i]
                
                if (j<m) // hat heap[i] auch einen rechten Sohn?
                        if (*heap[j-1] > *heap[j]) // und wenn ja, ist dieser rechte Sohn größer als der linke?
                                j++; // ... dann ist der Rechte Sohn maßgebend für die Heap-Eigenschaft

                if (*heap[i-1] > *heap[j-1])
                {
                        
                        // vertausche heap[i] und heap[j]; Heap-Eigenschaft ist dann "lokal" für heap[i] hergestellt;
                        t = heap[i-1]; heap[i-1] = heap[j-1]; heap[j-1] = t;

                        // heap[j] muss weiter versickern.
                        i = j;
                } else {

                        i = m;

                }

        }
};

template<class ItemClass> 
void heapify(ItemClass** heap, int length)
// stellt für die von heap[0]...heap[length-1] referenzierten Objekte die Heap-Eigenschaft her bzgl.
// ItemClass::operator> 
{
        
        for (int i=(length+1)/2; i>0; i--)
        {
                trickle<ItemClass>(heap, i, length);
        }
};


template<class ItemClass> 
void heapsort(ItemClass** heap, int length)
{
        heapify<ItemClass>(heap, length);

        for (int i=length-1; i>0; i--)
        {
                ItemClass* t = heap[i];
                heap[i] = heap[0];
                heap[0] = t;
                trickle<ItemClass>(heap, 1, i);
        }
};



template<class HeapClass> 
HeapClass* removeTopFromHeap(HeapClass** heap, int& length)
// entfernt das oberste Element vom Heap und liefert dieses als Ergebnis zurück.
// Das oberste Element bleibt in heap[length] erhalten; length wird
// um eins dekrementiert; dem verbleibenden Array der ersten (length-1) Objekte
// bleibt die Heap-Eigenschaft erhalten.
// > O(log (length)) Zeit und const Platz.
{
        HeapClass* first = heap[0];
        heap[0] = heap[length-1];
        heap[length-1] = first;
        
        length--;

        trickle<HeapClass>(heap, 1, length);

        return first;
};






/* ******************************************************************
   * Die folgende Implementierung entspricht fast der vorigen.      *
   * Der einzige unterschied besteht darin, dass diese Imple-       *
   * mentierung mit dem Typ Typ ItemClass* an Stelle von            *
   * ItemClass** arbeitet.                                          *
   ******************************************************************
*/


template<class ItemClass> 
void trickle(ItemClass* heap, int i, int m)
// Versickern von heap[i] bis max. heap[m]
{
        ItemClass t;
        int j;

        while (2*i <= m) // so lange heap[i] linken Sohn hat
        {
                
                j = 2*i; // heap[j] ist linker Sohn von heap[i]
                
                if (j<m) // hat heap[i] auch einen rechten Sohn?
                        if (heap[j-1] > heap[j]) // und wenn ja, ist dieser rechte Sohn größer als der linke?
                                j++; // ... dann ist der Rechte Sohn maßgebend für die Heap-Eigenschaft

                if (heap[i-1] > heap[j-1])
                {
                        
                        // vertausche heap[i] und heap[j]; Heap-Eigenschaft ist dann "lokal" für heap[i] hergestellt;
                        t = heap[i-1]; heap[i-1] = heap[j-1]; heap[j-1] = t;

                        // heap[j] muss weiter versickern.
                        i = j;
                } else {

                        i = m;

                }

        }
};

template<class ItemClass> 
void heapify(ItemClass* heap, int length)
// stellt für die von heap[0]...heap[length-1] referenzierten Objekte die Heap-Eigenschaft her bzgl.
// ItemClass::operator> 
{
        
        for (int i=(length+1)/2; i>0; i--)
        {
                trickle(heap, i, length);
        }
};


template<class ItemClass> 
void heapsort(ItemClass* heap, int length)
{
        heapify(heap, length);

        for (int i=length-1; i>0; i--)
        {
                ItemClass t = heap[i];
                heap[i] = heap[0];
                heap[0] = t;
                trickle(heap, 1, i);
        }
};



template<class HeapClass> 
HeapClass removeTopFromHeap(HeapClass* heap, int& length)
// entfernt das oberste Element vom Heap und liefert dieses als Ergebnis zurück.
// Das oberste Element bleibt in heap[length] erhalten; length wird
// um eins dekrementiert; dem verbleibenden Array der ersten (length-1) Objekte
// bleibt die Heap-Eigenschaft erhalten.
// > O(log (length)) Zeit und const Platz.
{
        HeapClass first = heap[0];
        heap[0] = heap[length-1];
        heap[length-1] = first;
        
        length--;

        trickle(heap, 1, length);

        return first;
};

}

#endif

The GroupIndex-Template-Library
Universität Bonn, Institut für Informatik III, 2001