堆操作.md

堆操作学习

　　堆的形态像树形结构，下面只考虑二叉堆。用数组的存储结构存储堆。那么需知道如下定义：
若X[0, N-1]表示一个堆，共有N个元素，那么

• X[0] 为堆顶
• value(i) = X[i]
• parent(i) = X[(i-1)/2]
• left_child(i) = X[2i+1]
• right_child[i] = X[2i+2]

根据上面的结论，可以方便的找到一个节点的父子节点。堆里面有两个重要函数：

1. X[0, n-1]满足堆的性质，末尾放入一个元素，让X[0, n]也满足堆性质，即下面代码的shfit_up函数
2. X[1, n]满足堆的性质，顶部放入一个元素，让X[0, n]也满足堆性质，即下面代码的shfit_down函数

堆的应用

1. 优先级队列
2. 堆排序，即便堆排序的时间复杂度为nlog(n),空间复杂度为O(1),但实际效果还是比快排慢。觉得应用在不用完全排序的地方比较好。

代码

/************************************************************
Copyright (C), 2016, Leon, All Rights Reserved.
FileName: heap.c
Description: 堆操作练习
Author: Leon
Version: 1.0
Date: 2016年11月7日09:53:51
Function:

History:
<author>    <time>  <version>   <description>
 Leon
************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 
  需清楚如下定义：
  X[0,N-1] 为一个堆，有N个元素
  X[0] 为堆顶
  parent(i) = X[(i-1)/2]
  left_child(i) = X[2i+1]
  right_child[i] = X[2i+2]
 */

/* 两个重要函数 */

/* heap(0,n-1) --> heap(0,n) , n为下标 */
void shift_up(int *X, int n)
{
    int parent;
    int i = n;
    int tmp;

    while(1)
    {
        parent = (i-1)/2;
        if(parent < 0)
            break;
        if(X[i] >= X[parent])
            break;
        tmp = X[i];
        X[i] = X[parent];
        X[parent] = tmp;

        i = parent;
    }
}

/* heap(1, n) --> heap(0,n) , n为下标*/
void shift_down(int *X, int n)
{
    int child;
    int i = 0;
    int tmp;

    while(1)
    {
        child = 2*i + 1;    //left child
        if(child > n)
            break;
        /* 找到最小的子节点 */
        if(child < n && X[child] > X[child+1])
            child++;

        if(X[i] <= X[child])
            break;

        tmp = X[i];
        X[i] = X[child];
        X[child] = tmp;

        i = child;
    }
}

void sort(int *array, int size)
{
    int i = 0;
    int tmp;

    /* 建堆 */
    for(i = 1; i < size; i++)
        shift_up(array, i);

    /* 排序，把堆顶最小值放到尾部，再重新生成堆 */
    for(i = size-1; i > 0; i--)
    {
        tmp = array[i];
        array[i] = array[0];
        array[0] = tmp;

        shift_down(array, i-1);
    }
}

void print_array(int *array, int size)
{
    int i = 0;

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

/* 因为是最小堆，逆序输出 */
void print_array_r(int *array, int size)
{
    int i = 0;

    for(i = size - 1; i >= 0; i--)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main(int argc, char *argv[])
{
    int n[100] = {0};
    int len = argc - 1; 
    int i;

    for(i = 1; i < argc && i <= 100; i++)
    {
        n[i-1] = atoi(argv[i]);
    }

    print_array(n, len);
    sort(n, len);
    print_array_r(n, len);

    return 0;
}

排序测试

root@ubuntu:soft_race# ./heap 1
1 
1 
root@ubuntu:soft_race# ./heap 1 2
1 2 
1 2 
root@ubuntu:soft_race# ./heap 2 1
2 1 
1 2 
root@ubuntu:soft_race# ./heap 2 1 3
2 1 3 
1 2 3 
root@ubuntu:soft_race# ./heap 1 2 3 4
1 2 3 4 
1 2 3 4
root@ubuntu:soft_race# ./heap 1236 123 2109 123612 213 43 1231293 12
1236 123 2109 123612 213 43 1231293 12 
12 43 123 213 1236 2109 123612 1231293