Skip to content

Instantly share code, notes, and snippets.

@nachinius
Last active October 20, 2016 20:07
Show Gist options
  • Save nachinius/490c1561a5bfe015ff18d8d4ac22cb84 to your computer and use it in GitHub Desktop.
Save nachinius/490c1561a5bfe015ff18d8d4ac22cb84 to your computer and use it in GitHub Desktop.
max heapify in C
cmake_minimum_required(VERSION 3.6)
project(algC)
#set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c")
set(SOURCE_FILES main.c)
add_executable(algC ${SOURCE_FILES})
//
// Created by nachinius on 10/20/16.
//
#include <stdlib.h>
#include <memory.h>
#include <printf.h>
#include <math.h>
typedef struct {
int *h;
int sizeOfHeap;
int sizeOfArray;
} heap_str;
heap_str * heap_init(size_t size) {
heap_str *h;
h = malloc(sizeof(heap_str *));
h->h = malloc(sizeof(int) * (1+size));
h->sizeOfArray = (int) size;
h->sizeOfHeap = 0;
return h;
}
void heap_free(heap_str *h) {
free(h->h);
free(h);
}
void swap(heap_str *h, int i, int j) {
int x;
x = h->h[j];
h->h[j] = h->h[i];
h->h[i] = x;
}
#define LEFT(i) (2*i)
#define RIGHT(i) (LEFT(i)+1)
void heap_maxify(heap_str *h, int i) {
int a,b;
int largest = i;
a = LEFT(i);
b = a + 1;
if(a <= h->sizeOfHeap && h->h[a] > h->h[i]) {
largest = a;
}
if(b <= h->sizeOfHeap && h->h[b] > h->h[largest]) {
largest = b;
}
if(largest != i) {
swap(h,i, largest);
heap_maxify(h, largest);
}
}
heap_str * heap_build(int *a, int size) {
heap_str *h;
h = heap_init(size);
memcpy((h->h)+1, a, sizeof(int) * size);
h->sizeOfHeap = size;
h->sizeOfArray = size;
for(int i=size/2; i>0;i--) {
heap_maxify(h,i);
}
return h;
}
void heap_print_array(heap_str *h) {
for(int i=1; i<=h->sizeOfHeap; i++) {
printf("%d, ",h->h[i]);
}
printf("\n");
}
#undef LEFT
#undef RIGHT
#include <stdio.h>
#include "heapify.c"
int main(int argc, char **argv) {
int i[5];
i[0] = 4/3;
i[1] = 5/3;
printf("%d %d\n",i[0],i[1]);
printf("------\n");
int a[16] = { 4, 3, 5, 1, 4, 10, 123, 3, 47, 11, 432,1,54,85,99};
heap_str *h;
h = heap_build(a, 15);
printf("array print\n");
heap_print_array(h);
free(h);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment