Mki's Blog

数据结构(六):堆与堆中的路径

题目描述

题目要求

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

基础知识

堆的概念

首先要搞清楚堆(Heap)是什么东西(注意,堆有别于堆栈,是两个概念)。堆也是一个二叉树,而且还是完全二叉树,不仅如此,它还是一个 具有优先级 的二叉树——类似搜索二叉树左节点小于父节点,右节点大于父节点,堆中节点的子节点都是大于(或者都是小于)父节点(大于的称为最大堆,反之称为最小堆)。

堆的操作

堆的创建

要创建一个堆,首先要知道数据的整理方式,是先排好序再往堆里面放,还是按输入顺序放好了再调整位置,这里我们选择后一种方式(后一种方式时间复杂度较低)。

此处自然就遇到一个问题,如何调整,联想到之前的考察二叉树同构的例子,不难想到利用递归的方法,从最底层的节点开始,向上调整。

首先,要创造一个数组,用来储存这些数值

H->Data = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType));

然后把值丢到树上 堆1.png

从最后一个有子节点的节点开始调整(这里的“到底”意思是说没有子节点比本身更大) 堆2.png

然后是上一个节点 堆3.png

再继续调节上一个节点,发现没到底,还可以继续调整。 堆4.png

最终完成 堆5.png

堆的删除

在我们进行删除操作的时候,一般是删除最大的那个节点或者最小的(想象一下,堆的本质就是一个有优先级的完全二叉树,既然有优先级,那么操作肯定是对于最优先或者最不优先,不然等级排序有什么意义呢,是吧?),也就是说,删除的操作是对堆的根进行的。那么,怎么操作会比较方便呢?

类似创建,这里也要用到节点比较下放的方法,较为独特的是,这里在删除根节点后,我们的操作是——把最后的节点放到根的位置上,然后比较下放。 1.把根103删去。 2.把最后一个节点44放到根的位置。 3.发现44的左右子节点都比自己大,那么挑一个最大的与44交换位置。 4.下放后的44的右子节点仍比自身大,接着下放。到底,完成。 6.png

堆的插入

插入一个值就是把它放在堆的末尾,然后跟前面的删除(从上往下比较)刚好相反,这里是反向,从下往上比较。直到上方“触顶”(即父节点比自己大)时停止。这里就不放图了,后面的操作集里有详细代码。

代码:堆的操作集

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

#define MAXDATA 1000   //预先设定可能会出现的最大值,当作“哨兵”
#define ERROR -1;

typedef struct HNode * Heap;
typedef int ElementType;

struct HNode {
    ElementType * Data;
    int Size;
    int Capacity;
};
typedef Heap MaxHeap;  //可以实现最大堆和最小堆的转化
typedef Heap MinHeap;

MaxHeap CreatHeap(int MaxSize) {  //创建一个堆
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType)); //这里+1是因为堆数组的0位不放这个堆的数值,拿来放无关的哨兵。
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MAXDATA;
    return H;
}

int IsFull(MaxHeap H) {
    return (H->Size == H->Capacity);
}

int Insert(MaxHeap H, ElementType X) {
    int i;
    if (IsFull(H)) {
        printf("最大堆已满");
        return 0;
    }
    i = ++H->Size;
    for (; H->Data[i] < X; i /= 2) {
        H->Data[i] = H->Data[i / 2];
    }
    H->Data[i] = X;
    return 1;
}

int IsEmpty(MaxHeap H) {   //判断
    return (H->Size == 0);
}

ElementType DeleteMax(MaxHeap H) {  //删除根的操作
    int Parent, Child;
    ElementType MaxItem, X;

    if (IsEmpty(H)) {
        printf("最大堆已为空");
        return ERROR;
    }

    MaxItem = H->Data[1];
    X = H->Data[H->Size--];
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1])) //还没到堆末尾,找左右节点更大值
            Child++;
        if (X >= H->Data[Child])
            break;
        else
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MaxItem;
}

void PercDown(MaxHeap H, int p) {   //数值下放操作
    int Parent, Child;
    ElementType X;
    X = H->Data[p];
    for (Parent = p; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
            Child++;
        if (X >= H->Data[Child])
            break;
        else
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}

void BuildHeap(MaxHeap H) {
    int i;
    for (i = H->Size / 2; i > 0; i--)
        PercDowna(H, i);
}

回到题目

咳咳,扯了这么多基础知识,那么接下来回归这个题目本身吧。 这个解题方法的关键一步就是上面说过的反向比较,触顶安放。即Insert()函数。

void Insert(int X) {
    int i;
    for (i = ++size; H[i / 2]>X; i /= 2)
        H[i] = H[i / 2];
    H[i] = X;
}

将二叉树调成最大堆的格式。

AC代码

#include<stdio.h>
#define MAXN 1001
#define MINH -10001

int H[MAXN], size;

void Create() {
    size = 0;
    H[0] = MINH;
}

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(void) {    //主函数
    int n, m, x, i, j;
    scanf_s("%d %d", &n, &m);
    Create();
    for (i = 0; i < n; i++) {
        scanf_s("%d", &x);
        Insert(x);
    }
    for (i = 0; i < m; i++) {
        scanf_s("%d", &j);
        printf("%d", H[j]);  //打印路径
        while (j > 1) {
            j /= 2;
            printf("%d", H[j]);
        }
        printf("\n");
    }
    return 0;
}

写在最后

  正值国庆,没有出去玩的打算(其实心里还是有那么一点想的,但是一个人出去好傻乎乎啊),杭州也是意料之中的挤,当然,下沙不算。不知道为什么,我觉得现在学校里的人数恰到好处,多一成显得拥挤,少一成显得冷清。   那天晚上煮面煮了好久,拿起筷子的时候突然想到,要是能请你吃面就好了。 1.jpg