堆排序

#include <stdio.h>

static int size = 0; // 当前数组即将插入元素的下标
static int a[10];// 存储

// swap function
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// push function
void max_heap_push(int v)
{
    a[size++] = v;

    int idx = size - 1;
    while (1)
    {
        if (idx == 0)  // root节点
        {
            break;
        }
        int parent = (idx - 1) / 2;

        if (a[idx] > a[parent])
        {
            swap(&a[idx], &a[parent]);
            idx = parent;
        } 
        else
        {
            break;
        }
    }
}

// pop And recover to heap  
int max_heap_pop()
{
    if (size == 0) {
        return -1;
    }

    int pop = a[0];
    
    size--;

    if (size == 0) {
        return pop;
    }
    
    a[0] = a[size];
    
    int idx = 0;
    while (1)
    {
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;

        if (left >= size && right >= size)
        {
            break;
        } 
        else if (right >= size && left < size)  // has only one child
        {
            if (a[idx] < a[left])
            {
                swap(&a[idx], &a[left]);
                idx = left;
            }
            else
            {
                break;
            }
        }
        else  // has both left and right children.
        {
            // find largest from a[idx, left, right]
            int largest_idx = idx;

            if (a[largest_idx] < a[left]) 
            {
                largest_idx = left;
            }

            if (a[largest_idx] < a[right]) 
            {
                largest_idx = right;
            }

            // swap
            if (largest_idx == idx)
            {
                break;
            }
            else if (largest_idx == left)
            {
                swap(&a[idx], &a[left]);
                idx = left;
            }
            else
            {
                swap(&a[idx], &a[right]);
                idx = right;
            }
        }

    }
    return pop;
}

void init_head(int array[], int len)
{
    for (int i = 0; i < len; ++i)
    {
        max_heap_push(array[i]);
    }
}

int main(int argc, char const *argv[])
{
    int array[5] = {1, 2, 3, 4, 5};

    init_head(array, 5);

    for (int i = 0; i < size; ++i)
    {
        printf("%d\n", a[i]);
    }

    printf("-->%d\n", max_heap_pop());

    for (int i = 0; i < size; ++i)
    {
        printf("%d\n", a[i]);
    }

    max_heap_push(6);

    for (int i = 0; i < size; ++i)
    {
        printf("-->%d\n", a[i]);
    }

    return 0;
}

数学模型
Parent(i) = floor((i-1)/2)，i 的父节点下标
Left(i) = 2i + 1，i 的左子节点下标
Right(i) = 2(i + 1)，i 的右子节点下标