Skip to content

Instantly share code, notes, and snippets.

@martinkunev
Created November 14, 2011 22:52
Show Gist options
  • Save martinkunev/1365481 to your computer and use it in GitHub Desktop.
Save martinkunev/1365481 to your computer and use it in GitHub Desktop.
Binary heap (C implementation)
// WARNING: Requires C99 compatible compiler
#include <unistd.h>
#include <stdlib.h>
#include "heap.h"
#define CMP(a, b) ((a) >= (b))
static const unsigned int base_size = 4;
// Prepares the heap for use
void heap_init(struct heap *restrict h)
{
*h = (struct heap){
.size = base_size,
.count = 0,
.data = malloc(sizeof(type) * base_size)
};
if (!h->data) _exit(1); // Exit if the memory allocation fails
}
// Inserts element to the heap
void heap_push(struct heap *restrict h, type value)
{
unsigned int index, parent;
// Resize the heap if it is too small to hold all the data
if (h->count == h->size)
{
h->size <<= 1;
h->data = realloc(h->data, sizeof(type) * h->size);
if (!h->data) _exit(1); // Exit if the memory allocation fails
}
// Find out where to put the element and put it
for(index = h->count++; index; index = parent)
{
parent = (index - 1) >> 1;
if CMP(h->data[parent], value) break;
h->data[index] = h->data[parent];
}
h->data[index] = value;
}
// Removes the biggest element from the heap
void heap_pop(struct heap *restrict h)
{
unsigned int index, swap, other;
// Remove the biggest element
type temp = h->data[--h->count];
// Resize the heap if it's consuming too much memory
if ((h->count <= (h->size >> 2)) && (h->size > base_size))
{
h->size >>= 1;
h->data = realloc(h->data, sizeof(type) * h->size);
if (!h->data) _exit(1); // Exit if the memory allocation fails
}
// Reorder the elements
for(index = 0; 1; index = swap)
{
// Find the child to swap with
swap = (index << 1) + 1;
if (swap >= h->count) break; // If there are no children, the heap is reordered
other = swap + 1;
if ((other < h->count) && CMP(h->data[other], h->data[swap])) swap = other;
if CMP(temp, h->data[swap]) break; // If the bigger child is less than or equal to its parent, the heap is reordered
h->data[index] = h->data[swap];
}
h->data[index] = temp;
}
// Heapifies a non-empty array
void heapify(type data[restrict], unsigned int count)
{
unsigned int item, index, swap, other;
type temp;
// Move every non-leaf element to the right position in its subtree
item = (count >> 1) - 1;
while (1)
{
// Find the position of the current element in its subtree
temp = data[item];
for(index = item; 1; index = swap)
{
// Find the child to swap with
swap = (index << 1) + 1;
if (swap >= count) break; // If there are no children, the current element is positioned
other = swap + 1;
if ((other < count) && CMP(data[other], data[swap])) swap = other;
if CMP(temp, data[swap]) break; // If the bigger child is smaller than or equal to the parent, the heap is reordered
data[index] = data[swap];
}
if (index != item) data[index] = temp;
if (!item) return;
--item;
}
}
// WARNING: Requires C99 compatible compiler
typedef int type;
struct heap
{
unsigned int size; // Size of the allocated memory (in number of items)
unsigned int count; // Count of the elements in the heap
type *data; // Array with the elements
};
void heap_init(struct heap *restrict h);
void heap_push(struct heap *restrict h, type value);
void heap_pop(struct heap *restrict h);
// Returns the biggest element in the heap
#define heap_front(h) (*(h)->data)
// Frees the allocated memory
#define heap_term(h) (free((h)->data))
void heapify(type data[restrict], unsigned int count);
@alldroll
Copy link

@NikkiKoole maybe you will try this

@xiaonanln
Copy link

@NikkiKoole binary heap only promise the the first element is minimal, not that the whole list is sorted. You understood wrongly.

@mucamaca
Copy link

mucamaca commented Feb 7, 2017

This code has some serious flaws.
What if someone tried to pop() an empty heap?
Or heapify() an array of length 1?
What about memory deallocation?

@ArtemShypotilov
Copy link

This code has some serious flaws.
What if someone tried to pop() an empty heap?
Or heapify() an array of length 1?
What about memory deallocation?

Totally agree. Got into that problems.

@martinkunev
Copy link
Author

martinkunev commented Oct 1, 2019

This is actually an old version but thanks for the feedback anyway.
@mucamaca Good catch about heapify() with length 1, I have actually fixed this in a later version.
about pop(), my intention when writing this was to suppose design by contract. I guess an abort() call inside pop() can be made in case the heap is empty.

Latest version is at https://gitlab.com/martinkunev/conquest_of_levidon/tree/2019/src/generic/

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment