path: root/heap.c

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "util.h"

typedef int T;

// https://stackoverflow.com/a/22900767

#define LEFT(idx) (idx * 2 + 1)
#define RIGHT(idx) (idx * 2 + 2)
#define PARENT(idx) ((idx - 1) / 2)

static void
swap(T heap[], size_t i, size_t j)
{
	T temp  = heap[i];
	heap[i] = heap[j];
	heap[j] = temp;
}

#define MAX_HEAP 1

#if defined(MAX_HEAP)
// MAX-HEAP Implementation
static void
fixup(T heap[], size_t i)
{
	size_t p = PARENT(i);

	while ( i > 0 && heap[p] < heap[i] ) {
		swap(heap, p, i);

		i = p;
		p = PARENT(i);
	}
}

static void
fixdown(T heap[], size_t i, size_t n)
{
	for ( ;; ) {
		const size_t l = LEFT(i);
		const size_t r = RIGHT(i);
		size_t       m = i;

		if ( l < n && heap[m] < heap[l] ) {
			m = l;
		}

		if ( r < n && heap[m] < heap[r] ) {
			m = r;
		}

		if ( m == i ) {
			break;
		}

		swap(heap, m, i);

		i = m;
	}
}

static bool
is_heap(T heap[], size_t n)
{
	for ( size_t i = 0; i < n / 2; ++i ) {
		const size_t l = LEFT(i);
		const size_t r = RIGHT(i);

		if ( l < n && heap[i] < heap[l] ) {
			return false;
		}
		if ( r < n && heap[i] < heap[r] ) {
			return false;
		}
	}
	return true;
}

#else
// MIN-HEAP Implementation
static void
fixup(T heap[], size_t i)
{
	size_t p = PARENT(i);

	while ( i > 0 && heap[i] < heap[p] ) {
		swap(heap, i, p);

		i = p;
		p = PARENT(i);
	}
}

static void
fixdown(T heap[], size_t i, size_t n)
{
	for ( ;; ) {
		const size_t l = LEFT(i);
		const size_t r = RIGHT(i);
		size_t       m = i;

		if ( l < n && heap[l] < heap[m] ) {
			m = l;
		}

		if ( r < n && heap[r] < heap[m] ) {
			m = r;
		}

		if ( m == i ) {
			break;
		}

		swap(heap, m, i);

		i = m;
	}
}

static bool
is_heap(T heap[], size_t n)
{
	for ( size_t i = 0; i < n / 2; ++i ) {
		const size_t l = LEFT(i);
		const size_t r = RIGHT(i);

		if ( l < n && heap[i] > heap[l] ) {
			return false;
		}
		if ( r < n && heap[i] > heap[r] ) {
			return false;
		}
	}
	return true;
}
#endif

static void
heapify(T heap[], size_t n)
{
	for ( size_t i = n / 2; i-- > 0; ) {
		fixdown(heap, i, n);
	}

	assert(is_heap(heap, n));
}

static void
my_heapsort(T a[], size_t n)
{
	heapify(a, n);

	while ( n-- ) {
		swap(a, 0, n);
		fixdown(a, 0, n);
	}
}

void
heapsort_bu(T *data, int n) // zu sortierendes Feld und seine Länge
{
	T   val;
	int parent, child;
	int root = n >> 1; // erstes Blatt im Baum

	for ( ;; ) {
		if ( root ) { // Teil 1: Konstruktion des Heaps
			parent = --root;
			val    = data[root]; // zu versickernder Wert
		}
		else if ( --n ) {      // Teil 2: eigentliche Sortierung
			val     = data[n]; // zu versickernder Wert vom Heap-Ende
			data[n] = data[0]; // Spitze des Heaps hinter den Heap in
			parent  = 0;       //   den sortierten Bereich verschieben
		}
		else // Heap ist leer; Sortierung beendet
			break;

		while ( (child = (parent + 1) << 1) < n ) // zweites (!) Kind;
		{                                         // Abbruch am Ende des Heaps
			if ( data[child - 1] > data[child] )  // größeres Kind wählen
				--child;

			data[parent] = data[child]; // größeres Kind nach oben rücken
			parent       = child;       // in der Ebene darunter weitersuchen
		}

		if ( child == n )                   // ein einzelnes Kind am Heap-Ende
		{                                   //   ist übersprungen worden
			if ( data[--child] >= val ) {   // größer als der zu versick-
				data[parent] = data[child]; //   ernde Wert, also noch nach oben
				data[child]  = val;         // versickerten Wert eintragen
				continue;
			}

			child = parent; // 1 Ebene nach oben zurück
		}
		else {
			if ( data[parent] >= val ) { // das Blatt ist größer als der
				data[parent] = val;      //   zu versickernde Wert, der damit
				continue;                //   direkt eingetragen werden kann
			}

			child = (parent - 1) >> 1; // 2 Ebenen nach oben zurück
		}

		while ( child != root ) // maximal zum Ausgangspunkt zurück
		{
			parent = (child - 1) >> 1; // den Vergleichswert haben wir bereits
			                           //   nach oben verschoben
			if ( data[parent] >= val ) // größer als der zu versickernde
				break;                 //   Wert, also Position gefunden

			data[child] = data[parent]; // Rückverschiebung nötig
			child       = parent;       // 1 Ebene nach oben zurück
		}

		data[child] = val; // versickerten Wert eintragen
	}
}

// -------------------------------------------

struct pq { // Priority Queue
	T      heap[251];
	size_t sz;
};

void
pq_init(struct pq *pq)
{
	pq->sz = 0;
}

bool
pq_push(struct pq *pq, T data)
{
	if ( pq->sz == NELEM(pq->heap) ) {
		return false;
	}

	pq->heap[pq->sz] = data;
	fixup(pq->heap, pq->sz);
	++pq->sz;
	return true;
}

bool
pq_pop(struct pq *pq, T *data)
{
	if ( pq->sz == 0 ) {
		return false;
	}

	*data = pq->heap[0];
	--pq->sz;
	pq->heap[0] = pq->heap[pq->sz];
	fixdown(pq->heap, 0, pq->sz);
	return true;
}

// -------------------------------------------

void
print_heap(T heap[], size_t n)
{
	if ( n ) {
		printf("%d", heap[0]);
		for ( size_t i = 1; i != n; ++i ) {
			printf(", %d", heap[i]);
		}
		putchar('\n');
	}
}

void
test_heapsort(void)
{
	static const size_t N = 1000000;
	T                   array[N];

	puts("fülle....");
	srand(time(NULL));
	for ( size_t idx = 0; idx != NELEM(array); ++idx ) {
		array[idx] = rand();
	}

	puts("sortiere....");
	clock_t start = clock();
	//my_heapsort(array, NELEM(array));
	heapsort_bu(array, NELEM(array));
	clock_t end = clock();

	puts("teste...");
	for ( size_t idx = 1; idx != NELEM(array); ++idx ) {
#if defined(MAX_HEAP)
		if ( array[idx - 1] > array[idx] ) {
			fprintf(stderr, "Fehler an Pos: %zu\n", idx);
			exit(EXIT_FAILURE);
		}
#else
		if ( array[idx - 1] < array[idx] ) {
			fprintf(stderr, "Fehler an Pos: %zu\n", idx);
			exit(EXIT_FAILURE);
		}
#endif
	}
	printf("ok! (%.3lf sec)\n", ((double) end - start) / CLOCKS_PER_SEC);
}

void
test_pq(void)
{
	struct pq pq[1];

	pq_init(pq);

	for ( int i = 0; i != 10; ++i ) {
		pq_push(pq, rand());
	}

	T data;
	while ( pq_pop(pq, &data) ) {
		printf("%d\n", data);
	}
}

int
main(void)
{
	test_heapsort();
	test_pq();
#if 1 // Heap-Testprogramm
	// Beispiel aus "Informatik - Datenstrukturen und Konzepte der Abstraktion"
	// Kapitel 5.10, Seite 372 ff.
	T heap[20] = { 18, 18, 16, 9, 7, 1, 9, 3, 7, 5 };

	//heapify(heap, 10);
	assert(is_heap(heap, 10));
	print_heap(heap, 10);

	//heap[10] = 13; fixup(heap, 10);
	swap(heap, 0, 9);
	fixdown(heap, 0, 9);

	assert(is_heap(heap, 9));
	print_heap(heap, 9);
#endif
}