Priority Queue

struct PriorityQueue

#define MAX 100
typedef struct PriorityQueue{
	int size;
	int arr[MAX];
}PriorityQueue;
Priority Queue

function initial

void initial(PriorityQueue *q){
	q -> size = 0;
}
Priority Queue

function isEmpty

bool isEmpty(const PriorityQueue *q){
	return q -> size <= 0;
}
Priority Queue

function isFull

bool isFull(const PriorityQueue *q){
	return q -> size >= MAX;
}
Priority Queue

function swap

void swap(int arr[], int i, int j){
	int t = arr[i];
	arr[i] = arr[j];
	arr[j] = t;
}
Priority Queue

function

void heapifyUp(int arr[], int k){
	int p;
	while( k > 0){
		p = (k - 1) / 2;
		if (arr[k] < arr[p]){
			break;
		}
		swap(arr, k, p);
		k = p;
	}
}
Priority Queue

function enqueue

bool enqueue(PriorityQueue *q, int x){
	if (isFull(q)){
		return false;
	}else{
		q -> arr[q -> size ++] = x;
		heapifyUp(q -> arr, q->size - 1);
		return true;
	}
}
Priority Queue

function peek

int peek(const PriorityQueue *q){
	if (isEmpty(q)){
		exit(0);
	}
	return q->arr[0];
}
Priority Queue

function heapifyDown

void heapifyDown(int arr[], int l, int r){
	int k = 2 * l + 1;
	while ( k <= r){
		if (k < r && arr[k] < arr[k + 1]){
			k ++;
		}
		if (arr[l] > arr[k]){
			break;
		}
		swap(arr, l, k);
		l = k;
		k = 2 * l + 1;
	}
}
Priority Queue

function dequeue

int dequeue(PriorityQueue* q){
	if (isEmpty(q)){
		exit(0);
	}else{
		int x = q -> arr[0];
		q -> size --;
		swap(q -> arr, 0, q -> size);
		heapifyDown(q -> arr, 0, q -> size - 1);
		return x;
	}
}
Priority Queue

function main

void main(){
	PriorityQueue q;
	initial(&q);
	enqueue(&q, 7);
	enqueue(&q, 2);
	enqueue(&q, 8);
	enqueue(&q, 1);
	enqueue(&q, 6);
	enqueue(&q, 4);
	while(!isEmpty(&q)){
		printf("%d ", dequeue(&q));
	}
}