algos

heap.c

#include <stdio.h>

const int MAXN = 10000000;

int heap[MAXN+1];
int heapSize;

int n;

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// heap sort

void swim(int x) {
    if (x == 1) {
        return;
    }
    int fa = x>>1;
    if (heap[fa] > heap[x]) {
        swap(&heap[fa], &heap[x]);
        swim(fa);
    }
}

// TODO: implement swim with loop

void sink(int x) {
    int l = x<<1;
    int r = x<<1|1;
    if (l > heapSize) {
        return;
    } else if (r > heapSize) {
        if (heap[l] < heap[x]) {
            swap(heap + l, heap + x); // == swap(&heap[l], &heap[x]);
        }
    } else {
        int t = l;
        if (heap[r] < heap[t]) {
            t = r;
        }
        if (heap[t] < heap[x]) {
            swap(heap + t, heap + x);
            sink(t);
        }
    }
}


void insert(int val) {
    heap[++heapSize] = val;
    swim(heapSize);
}

void buildHeap() {
    for (int i = 1; i <= n; ++i) {
        swim(i);
    }
    heapSize = n;
}


int popTop() {
    int r = heap[1];
    swap(heap + 1, heap + heapSize);
    --heapSize;
    sink(1);
    return r;
}

int main() {
    // input n
    // n elements
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", heap + i);
    }
    buildHeap();
    // output, n elements sorted
    for (int i = 0; i < n; ++i) {
        printf("%d ", popTop());
    }
    puts("");
}