数据结构——堆（C代码实现）

淡淡的烟草味﹌ 2022-12-27 02:14 177阅读 0赞

### 目录 ###

*  堆的结构定义
 *  堆的结构操作
 *  大顶堆代码实现

# 堆的结构定义 #

堆本质上可以看作是一棵`完全二叉树`，如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTY1NTM3_size_16_color_FFFFFF_t_70_pic_center]

>   存储数据的空间为一段连续的空间，类似于数组，实际上也确实是用动态数组存的数据，假设根结点下标为`i`，则它的左孩子下标为`2 * i + 1`，右结点下标为`2 * i + 2`。上图表示为数组则是这样的：`heap[13] = {20, 18, 16, 12, 8, 10, 14, 3, 5, 6, 4, 7, 2}`

>   堆的数据空间维护了一种特殊的性质，那就是第一个数一定是所有数据最大或最小的，首位最大则为大顶堆，首位最小则为小顶堆。

# 堆的结构操作 #

1.  堆的初识化`init()`：动态开辟一段存储空间，记录空间的大小，存储数据的个数。
2.  插入数据`push()`：将新数据插入到堆的最后，再通过不断地与该数据所在位置的父结点比较，以大顶堆为例，新数据比父结点数据大，则交换两个数据的存储位置，直至把新数据放到合适的位置。
3.  删除堆顶数据`pop()`：将堆的最后一个数据放到堆顶，覆盖掉堆顶数据，将堆的数据个数减1，然后现在的堆顶数据通过不断地与左结点和右结点比较，以大顶堆为例，将这3个数中最大的数据交换到父结点位置上，直至把新堆顶数据放到合适地位置。
4.  堆的扩容`expand()`：用`realloc()`函数开辟新的动态数组空间。
5.  获取堆顶数据`top()`：直接返回数据空间中第一位的数据。

# 大顶堆代码实现 #

#include <stdio.h>
    #include <stdlib.h>
    
    //交换两个变量的值
    #define swap(a, b) {\
    	__typeof(a) __temp = a;\
    	a = b;\
    	b = __temp;\
    }
    
    //堆的结构定义
    typedef struct Heap {
        
        int *data;//数据空间
        int size, cnt;//空间大小，数据的个数
    } Heap;
    
    //堆的初始化
    Heap *init(int n) {
        
        //开辟堆结构所需要的空间。
        Heap *h = (Heap *)malloc(sizeof(Heap));
        //开辟数据空间，大小为n
        h->data = (int *)malloc(sizeof(int) * n);
        //空间大小为n，数据个数为0
        h->size = n;
        h->cnt = 0;
        return h;
    }
    
    //堆的扩容
    int expand(Heap *h) {
        
        //临时指针，保存扩容后空间的地址
        int *p = NULL;
        //要增加的空间大小
        int extr_size = h->size;
        //当p不为空地址，则扩容成功
        while (extr_size != 0) {
        
            p = (int *)realloc(h->data, sizeof(int) * (h->size + extr_size));
            if (p != NULL) break;
            extr_size /= 2;
        }
        if (p == NULL) return 0;
        //扩容成功，更新数据空间的地址，以及空间的大小
        h->data = p;
        h->size += extr_size;
        return 1;
    }
    
    int push(Heap *h, int val) {
        
        if (h == NULL) return 0;
        if (h->cnt == h->size) {
        
            if (expand(h) == 0) return 0;
        }
        //数据插入堆，堆的数据个数增加1
        h->data[(h->cnt)++] = val;
        //维护大顶堆的性质
        int ind = h->cnt - 1;
        //从插入位置开始，不断向上与父结点比较，直至新数据放到合适位置。
        while ((ind - 1) / 2 >= 0 && h->data[ind] > h->data[(ind - 1) / 2]) {
        
            swap(h->data[ind], h->data[(ind - 1) / 2]);
            ind = (ind - 1) / 2;
        }
        return 1;
    }
    
    int pop(Heap *h) {
        
        if (h == NULL) return 0;
        if (h->cnt == 0) return 0;
        //堆尾数据覆盖堆首数据，堆的数据个数减少1
        h->data[0] = h->data[--(h->cnt)];
        //维护大顶堆的性质
        int ind = 0;
        //从堆首开始，不断向下与左右结点比较，直至刚开始维护的堆首数据放到合适的位置。
        while (ind * 2 + 1 < h->cnt) {
        
            int temp = ind, left = ind * 2 + 1, right = ind * 2 + 2;
            if (h->data[left] > h->data[temp]) temp = left;
            if (right < h->cnt && h->data[right] > h->data[temp]) temp = right;
            //没有交换，则所有数据的位置都是合适的，退出循环
            if (temp == ind) break;
            //交换了，则从交换的子结点位置开始向下维护
            swap(h->data[ind], h->data[temp]);
            ind = temp;
        }
        return 1;
    }
    
    int top(Heap *h) {
        
    	return h->data[0];
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTY1NTM3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e700dcd8f1c44d1c81f540b6dca40179.png