pq

pq.c

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

#define LENGTH 10

struct node
{
	int priority;
	int time;

	int data;
};


int left(int i) { return 2*i; }
int right(int i){ return 2*i+1; }

void heapify(int arr[], int i){
	int l = left(i),
			r = right(i),
			arrSize = LENGTH,
			largest;


	largest = ( l <= arrSize && arr[l] > arr[i]  ) ? l : i;

	if(r <= arrSize && arr[r] > largest ) largest = r;

	if(largest != i){
		int t        = arr[i];
		arr[i]       = arr[largest];
		arr[largest] = t;

		heapify(arr, largest);
	}

}

void build_heap(int arr[]){
	int i;

	for(i = LENGTH; i <= 2 ; i--){
		int t  = arr[1];
		arr[1] = arr[i];
		arr[i] = t;

		heapify(arr, 1);
	}

}

void printr(int arr[]){
	int i;
	for(i = 0; i < LENGTH; i++)
		printf("%d, ", arr[i]);
}

int main()
{

	int arr[LENGTH] = { 16,10,15,4,12,13,5,9,2,8 };


	printf("Before heap: \n");
	printr(arr);
	printf("\n");
	//prints:  16, 10, 15, 4, 12, 13, 5, 9, 2, 8

	build_heap(arr);

	printf("After heap: \n");
	printr(arr);

	// prints: 16, 10, 15, 4, 12, 13, 5, 9, 2, 8
	// should: 16, 12, 15, 9, 10, 13, 5, 4, 2, 8

	return 0;
}