深入浅出堆—C语言版【数据结构】

二叉树概念博客：http://t.csdn.cn/XIW84

1. 了解堆

1.1 堆的概念

1.2 堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

1.3 堆的结构图片

1.3.1 小堆

满足下面条件的是小堆

1.3.2 大堆

满足下面条件的是大堆

注意不一定是从大到小、从小到大存储的！！！

---

堆有什么作用呢？

下面来细讲，别走开！！！

2. 堆的实现

2.1 插入数据进堆

void HeapPush(HP* php, HPDataType x)
{
    assert(php);
    if (php->size == php->capacity)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }

        php->a = tmp;
        php->capacity = newcapacity;
    }

    php->a[php->size] = x;
    php->size++;

    AdjustUp(php->a, php->size - 1);
}

注意点！！！

假如一开始我们的堆是小堆，但是在插入数据以后要保持还是小堆，要将插入的数据的大小和它的父亲进行比较，比较的两种情况：

1. 如果插入的数据比父亲还要大，那就不需要调整

2. 如果插入的数据比父亲还要小，那就需要调整

如果需要调整，我们就要使用向上调整算法，保持插入数据后的堆还是小堆

2.2 向上调整函数

void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;//求出插入数据的父亲位置下标
    
    while (child > 0)
    {
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;//将父亲的下标给孩子，向上调整
            parent = (child - 1) / 2;//再算出此时插入数据的父亲下标
        }
        else
        {
            break;
        }
    }
}

2.3 堆的删除

能不能使用覆盖删除呢—不能！！！

使用覆盖删除，会打乱父子之间的下标关系，父子关系就会全部乱掉，因此我们使用下面的方法来删除数据

---

1. 先将下标为0位置的数据和下标最大的数据进行交换

2. 然后直接size--

3. 然后还需要使用向下调整算法，把堆再调整为小堆

void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    Swap(&(php->a[0]), &(php->a[php->size - 1]));1.交换
    php->size--;//2. 删除堆顶元素

    AdjustDwon(php->a, php->size, 0);//向下调整，保证还是小堆
}

2.4 向下调整

void AdjustDwon(HPDataType* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        // 选出左右孩子中小那个
        //这里的if里面的判断大小尽量写成小于是小堆，大于是大堆
        if (child+1 < size && a[child+1] < a[child])
        {
            ++child;
        }

        // 孩子跟父亲比较
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }    
}

3. 堆的应用

3.1 建堆（两种方式）

3.1.1 建堆方式1

利用插入元素的方式，向上调整建堆

void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;
    
    while (child > 0)
    {
        //if (a[child] < a[parent])
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
/

void HeapSort(int* a, int n)//传一个数组过来，还有元素个数
{
    // 建堆方式1：O(N*logN)
    for (int i = 1; i < n; ++i)
    {
        AdjustUp(a, i);//从插入的第二个元素开始
    }
}

建堆方式1的时间复杂度 ——错位相减法

3.1.2 建堆方式2

利用向下调整建堆

方法：找到最后一个元素的父亲，并从这个位置开始向下调整

void HeapSort(int* a, int n)
{

    // 建堆方式2：O(N)
    for (int i = (n-1-1)/2; i >= 0; --i)
    {
        AdjustDwon(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDwon(a, end, 0);
        --end;
    }
}

建堆方式2的时间复杂度——错位相减法

3.2 堆排序

排升序，建大堆，再向下调整

为什么建大堆呢？

建大堆，堆顶元素是最大的数，让堆顶元素和最后一个元素交换，再向下调整，注意：这里向下调整时是调整的数组大小-1个，也就是调整刚刚交换下来前面的数据

---

排降序，建小堆，再向下调整

void HeapSort(int* a, int n)
{

    // 建堆方式2：O(N)
    for (int i = (n-1-1)/2; i >= 0; --i)
    {
        AdjustDwon(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);//这里的end是9，传过去向下调整的元素个数也是9，
                             //就不会调整刚刚从堆顶传下来的数据
        AdjustDwon(a, end, 0);
        --end;
    }

3.3 堆的TOP—K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

实现思路：

这样空间复杂度非常小

---

注意：

   **    求前k个最大的数，是建小堆**

       解释：由于建立的前k个数是小堆，后面n-k个数都可能比对顶的数值大，比堆顶的元素大，就替换堆顶的元素，然后再向下调整，保持前k个数是小堆，然后再比较····

      ** 求前k个最小的数，是建大堆（同上**）

代码实现：

void PrintTopK(int* a, int n, int k)
{
    // 1. 建堆--用a中前k个元素建堆
    int* kMinHeap = (int*)malloc(sizeof(int)*k);
    assert(kMinHeap);
    for (int i = 0; i < k; ++i)//将a数组里面前10个数赋值给KMinHeap
    {
        kMinHeap[i] = a[i];
    }
    for (int i = (k - 1 - 1) / 2; i >= 0; --i)//向下调整建堆，建立k个数的小堆
    {
        AdjustDwon(kMinHeap, k, i);
    }

    // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    for (int j = k; j < n; ++j)
    {
        if (a[j] > kMinHeap[0])
        {
            kMinHeap[0] = a[j];
            AdjustDwon(kMinHeap, k, 0);//再向下调整，保持前k个数是小堆
        }
    }

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

void TestTopk()
{    
    //随机生成一万个数字，每个数字%1百万，这一万都是比一百万小的数字，
    //我们将其中的10个数改为比一百万大的值
    int n = 10000;
    int* a = (int*)malloc(sizeof(int)*n);
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;
    }
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[5121] = 1000000 + 4;
    a[120] = 1000000 + 5;
    a[99] = 1000000 + 6;
    a[0] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[3144] = 1000000 + 10;

    PrintTopK(a, n, 10);
}

本文讲的是二叉树的顺序存储结构（堆）的实现，下期我们来讲二叉树的链式存储结构，到时候记得来支持小余哦！！！

如果觉得文章不错，期待你的一键三连哦，你个鼓励是我创作的动力之源，让我们一起加油，顶峰相见！！！