Heap

heap.c

#include <stdio.h>
#include <stdlib.h>

#define swap(type, x ,y) do {type t = x; x = y; y = t;} while(0)
#define N 50 // ヒープの最大サイズ．

void shiftdown ( int* heap, int parent, int n )
{
	int child;

	child = parent * 2 + 1;

	while ( child <= n )
	{
		// 右の子の方が左の子より大きければ着目を右に移す．
		if ( child < n && heap[child] < heap[child+1] )
		{
			child++;
		}

		// 親のほうが子より小さければ交換
		if ( heap[parent] < heap[child] )
		{
			swap ( int, heap[parent], heap[child] );
		}

		parent = child;

		child = parent * 2 + 1;
	}
}

void shiftup ( int* heap, int n )
{
	int child = n;
	int parent = ( n - 1 ) / 2;

	while ( heap[child] > heap[parent] && child > 0 )
	{
		swap ( int, heap[child], heap[parent] );

		child = parent;

		parent = ( child - 1 ) / 2;
	}
}

void add ( int* heap, int element, int* n )
{
	*n += 1;

	int index = *n;

	heap[index] = element;

	shiftup ( heap, index );
}

void init_heap ( int* heap, int n )
{
	int i;
	for ( i = ( n - 1 ) / 2; i >= 0; i-- )
	{
		shiftdown ( heap, i, n );
	}
}

int delete_top ( int* heap, int* n )
{
	int ret = heap[0];

	heap[0] = heap[*n];

	*n -= 1;

	shiftdown ( heap, 0, *n );

	return ret;
}

int main ( void )
{
	int a[N];
	int n;

	n = -1; //最後のインデックスを保存．

	int i = 0;
	for ( i = 0; i < 30; i++ )
	{
		// a[i] = rand ()%1000;
		int r = rand()%100;
		add ( a, r, &n );
	}


	printf ( "生成したヒープの配列を表示\n" );
	for ( i = 0; i <= n; ++i )
	{
		printf ( "%d ", a[i] );
	}
	printf ( "\n" );

	int* sorted_array;

	sorted_array = calloc ( n + 1, sizeof ( int ) );
	int sorted_array_size = n + 1;

	while ( n != -1 )
	{
		int index = n;

		sorted_array[index] = delete_top ( a, &n );
	}

	printf ( "ソート後の要素の表示\n" );
	for ( int i = 0; i < sorted_array_size; ++i )
	{
		printf ( "%d ", sorted_array[i] );
	}
	printf ( "\n" );
}