Last active
October 20, 2016 20:07
-
-
Save nachinius/490c1561a5bfe015ff18d8d4ac22cb84 to your computer and use it in GitHub Desktop.
max heapify in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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}) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// 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 | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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