Priority queue

priority_queue.c

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


static inline void swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

static void show(int *nums, int size)
{
        int i;
        for (i = 0; i < size; i++) {
                printf("%d ", nums[i]);
        }
        printf("\n");
}

static void min_heapify(int *nums, int size, int parent)
{
    int i = parent;  /* parent is the root */
    int l = parent * 2 + 1;
    int r = parent * 2 + 2;

    if (l < size && nums[l] < nums[i]) {
        i = l;
    }

    if (r < size && nums[r] < nums[i]) {
        i = r;
    }

    /* percolate up */
    if (i != parent) {
        swap(&nums[i], &nums[parent]);
        min_heapify(nums, size, i);
    }
}

static void build_min_heap(int *nums, int size)
{
    int i;
    for (i = size / 2; i >= 0; i--) {
        min_heapify(nums, size, i);
    }
}

int main(void)
{
        int i, nums[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
        int size = sizeof(nums)/sizeof(*nums);
        build_min_heap(nums, size);
        show(nums, size);

        return 0;
}