堆(Heap)的实现

小咪咪 2022-04-12 04:38 226阅读 0赞

什么是堆？

优先队列（Opriority Queue）

特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70][]

堆有两大特性：

1，结构性：是一颗完全二叉树。

2， 有序性：每个叶子结点到根结点都是有序的，如果是升序，那么就是最大堆，否则为最小堆。

这些是堆：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 1][]

下面的不是堆：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 2][]

下面让我们来具体的来看堆是如何建立的

比如给定一组数据：46，25，26，24，10

我们应该如何画出这个最小堆和最大堆呢？

下面我们先说下最小堆的做法：

第一个元素46，我们直接插入

第二个元素25，我们和46比较，如果比46大，那么我们直接插入，否则和46换个位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 3][]

第三个元素26，和它的父亲结点23比较，比23大，所以我们直接插入。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 4][]

第4个元素24，和它的父亲结点46比较，比46小，交换

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 5][]

最后一个元素10，和它的父亲结点23比较，比2小，交换，然后和46比较，比46小，交换，但是46比它的儿子结点大，所以找到儿子结点中最小的，然后交换

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 6][]

下面是具体的代码实现

05-树7 堆中的路径 （25 分）

将一系列给定数字插入一个初始为空的小顶堆`H[]`。随后对任意给定的下标`i`，打印从`H[i]`到根结点的路径。

### 输入格式: ###

每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间\[-10000, 10000\]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

### 输出格式: ###

对输入中给出的每个下标`i`，在一行中输出从`H[i]`到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。

### 输入样例: ###

5 3

46 23 26 24 10

5 4 3

### 输出样例: ###

24 23 10

46 23 10

26 10

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    #define MAX 1001
    #define MIN -1001
    
    int H[MAX];
    int size;
    
    void Create()
    {
        size = 0;
        H[0] = MIN;//哨兵
    }
    
    void Insert(int x)
    {
        int i;
        for ( i = ++size; H[i/2] > x; i /=2)
            H[i] = H[i/2];
        H[i] = x;
    }
    
    int main()
    {
        int num,m, i, x, seq;
        cin >> num >> m;
    
        Create();
        for (i = 0; i < num; i++){
            cin >> x;
            Insert(x);
        }
    
        for ( i = 0; i < m; i++){
            cin >> seq;
            cout << H[seq];
            while(seq > 1){
                seq /= 2;
                cout << ' ' << H[seq];
            }
            cout << endl;
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70]: /images/20220412/609878567dc24bffba91fd09e5980750.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 1]: /images/20220412/2243e07069f044c1935c98a9822acfe8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 2]: /images/20220412/a99df5ffaa1045b9af20a74b427fdace.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 3]: /images/20220412/99b61f34c848429584a980517087d94c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 4]: /images/20220412/5c0146fe356f49ee8b0ba3bebcfaafb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 5]: /images/20220412/8b9f20f692b1474f849aa609eba01416.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70 6]: /images/20220412/9bbb2e3558204a40937cef7125c9d0e2.png