堆与优先队列

1 概念

• 堆：即优先队列，是基于完全⼆叉树所定义的一种新的数据结构，其要求完全二叉树中的任意三元组的根节点都是极大（小）值，并且树的根节点是最大（小）值。

2 分类

• ⼤顶（根）堆：在堆中，任意三元组中的根节点都是极⼤值，其可以求取全局最大值、全局次最大值。
• ⼩顶（根）堆：在堆中，任意三元组中的根节点都是极小值，其可以求取全局最小值、全局次最小值。

3 建堆方法

• 利用数组表示一颗完全二叉树，其表示关系为：根节点i，左孩子2i，右孩子2i+1，i≥1。

3.1 堆尾插入元素建堆法（自顶向下）

• 条件：事先不知道有多少个元素，通过动态的往堆里面插入元素进行调整来构建堆。
• 构建过程：（堆调整顺序：自下向上）
  1. 在堆尾插入新的元素；
  2. 当前元素存在父节点，执行步骤3，否则建堆结束；
  3. 比较当前元素和它的父结点值；如果当前元素比父节点值大，则交换两个元素（大顶堆），并继续执行步骤2，否则建堆结束。
• 大顶堆插入元素示意图：

• 经过堆调整后的结果展示：

• 从图中可以看出，从堆尾插入元素并进行堆结构调整，其时间复杂度为o(lgn)，n为节点个数；

3.2 线性建堆法（自下向上的）

• 条件：堆元素已经确定好的情况下，使用线性建堆法，如堆排序；
• 构建过程：
  1. 找到最后1个元素的父节点（parent_node ），即当前堆大小的一半（n/2），记作parent_node = n >> 2，n为堆中的节点大小；
  2. 从parent_node = （n / 2）位置开始，自上向下的调整堆结构，直到parent_node = 0为止；（遍历条件：1 ≤ parent_node ≤ n / 2 ）
• 大顶堆建堆示意图：

  

3.3 两种建堆方法的时间复杂度分析

在树高为h的二叉树中，根节点为第1层，每层的节点数量为2^(N-1)，其中N为每层的编号，N∈[1, h]。

• 树的高度与节点关系为：

sn=h∑N=12(N−1)=20+21+22+…+2(h−2)+2(h−1)=2h−1,N∈[1,h]��=∑�=1ℎ2(�−1)=20+21+22+…+2(ℎ−2)+2(ℎ−1)=2ℎ−1,�∈[1,ℎ]

h=log2(sn+1)ℎ=���2(��+1)

3.3.1 插入建堆法的时间复杂度分析– o(n*logn)

T=(N−1)∗2(N−1)+(N−2)∗2(N−2)+(N−3)∗2(N−3)+….+1∗21+0∗20�=(�−1)∗2(�−1)+(�−2)∗2(�−2)+(�−3)∗2(�−3)+….+1∗21+0∗20

• 上式中，每项的第1个参数：该节点向上调整的次数，每项的第2个参数：该层的节点数目；如第1项，(N-1)*2^(N-1) 表示第N层有2^(N-1)个节点需要经过(N-1)次向上堆调整过程。

T′=2∗T=(N−1)∗2N+(N−2)∗2(N−1)+(N−3)∗2(N−2)+….+1∗22+0∗21�′=2∗�=(�−1)∗2�+(�−2)∗2(�−1)+(�−3)∗2(�−2)+….+1∗22+0∗21

T=T′−T=(N−1)∗2N−(2(N−1)+2(N−2)+….+22+21)=(N−1)∗2N+(2−2N)=N∗2N+2(N+1)+2�=�′−�=(�−1)∗2�−(2(�−1)+2(�−2)+….+22+21)=(�−1)∗2�+(2−2�)=�∗2�+2(�+1)+2

o(T)=o(h∗2h−2(h+1)+2)≈o(h∗2h)=o((sn+1)∗log2(sn+1))=o(nlog2n)�(�)=�(ℎ∗2ℎ−2(ℎ+1)+2)≈�(ℎ∗2ℎ)=�((��+1)∗���2(��+1))=�(����2�)

3.3.2 线性建堆法的时间复杂度分析：- o(n)

T=0∗2(N−1)+1∗2(N−2)+2∗2(N−3)+….+(N−2)∗21+(N−1)∗20�=0∗2(�−1)+1∗2(�−2)+2∗2(�−3)+….+(�−2)∗21+(�−1)∗20

• 上式中，每项的第1个参数：该层节点向下调整的次数，每项的第2个参数：该层的节点数目

T′=2∗T=1∗2(N−1)+2∗2(N−2)+….+(N−2)∗22+(N−1)∗21�′=2∗�=1∗2(�−1)+2∗2(�−2)+….+(�−2)∗22+(�−1)∗21

T=T′−T=2(N−1)+2(N−2)+….+22+21−(N−1)∗20=2N−N−1�=�′−�=2(�−1)+2(�−2)+….+22+21−(�−1)∗20=2�−�−1

o(T)=o(2h−h−1)≈o(2h)=o(sn+1)=o(n)�(�)=�(2ℎ−ℎ−1)≈�(2ℎ)=�(��+1)=�(�)

• 时间复杂度结论：插入建堆 — o(nlgn)，线性建堆 — o(n)，n为节点个数

4 删除堆顶元素- o(logn)

• 删除步骤：
  1. 用堆尾元素替换堆顶元素，并将堆大小减1；
  2. 自上向下的调整堆结构，保证任意一个三元组都满足堆性质；
  3. 在当前节点编号大于节点数量 或 调整堆结构已发现满足堆性质时，停止调整，否则继续执行步骤2。
• 删除堆顶元素的示意图：

• 结论：删除堆顶元素需要自上向下调整堆结构，其时间复杂度为o(lgn)，n为节点数目

5 堆排序 – o(n*logn)

• 堆排序步骤：
  1. 将堆顶元素与堆尾元素交换；
  2. 对前n-1元素重新建堆；（与删除堆顶元素后的堆调整过程一样）
  3. 重复1、2 两个过程，直到堆中的元素为1时停止；
• 结论：采取大顶堆的调整方式，为升序排序；而采取小顶堆的调整方式，为降序排序。

6 代码演示

6.1 插入建堆法

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

#define SWAP(a, b) {
    __typeof(a) __temp = a; a = b; b = __temp;
}

typedef struct priority_queue {
    int *data;
    int cnt, size;  // cnt：堆中的元素个数，size：堆空间的容量
} priority_queue;

priority_queue* init(int size) {
    priority_queue* q = (priority_queue*)malloc(sizeof(priority_queue));
    // 多申请1个空间，是因为堆顶元素的编号为1，这样在建堆过程中可以减少1次加法运算
    q->data = (int*)malloc((size + 1) * sizeof(int));
    q->cnt = 0;
    q->size = size;

    return q;
}

int empty(priority_queue* q) {
    return q->cnt == 0;
}

// 获取堆顶元素
int top(priority_queue* q) {
    return q->data[1];
}

// 堆尾插入元素
int push(priority_queue* q, int v) {
    if (q == NULL) return 0;
    if (q->cnt == q->size) return 0;
    // 将元素插入堆尾
    q->data[++(q->cnt)] = v;
    // 重新调整堆结构（大顶堆）--- 自下向上
    int ind = q->cnt;   // 获取当前元素的编号
    while (ind >> 1 && q->data[ind] > q->data[ind >> 1]) {
        SWAP(q->data[ind], q->data[ind >> 1]);
        ind = ind >> 1;
    }
    return 1;
}

// 删除堆顶元素
int pop(priority_queue* q) {
    if (q == NULL) return 0;
    if (q->cnt == 0) return 0;
    // 将堆尾元素赋值堆顶
    q->data[1] = q->data[(q->cnt)--];
    // 重新调整堆结构（大顶堆）--- 自上向下
    int ind = 1;    // 堆顶元素的编号
    while ((ind << 1) <= q->cnt) {
        int temp = ind, lnode = ind << 1, rnode = ind << 1 | 1;
        if (q->data[temp] < q->data[lnode]) temp = lnode;
        if (rnode <= q->cnt &amp;&amp; q->data[temp] < q->data[rnode]) temp = rnode;
        if (temp == ind) break; // 当前三元组结构未发生变化
        SWAP(q->data[temp], q->data[ind]);
        ind = temp;
    }
    return 1;
}

void clear(priority_queue* q) {
    if (q == NULL) return ;
    if (q->data) free(q->data);
    free(q);
}

int main() {
    srand(time(0));
    const int N = 10;
    priority_queue* q = init(N);
    for (int i = 1; i <= N; i++) {
        int v = rand() % 100;
        push(q, v);
    }

    for (int i = 1; i <= q->cnt; i++) {
        printf("%d ", q->data[i]);
    }
    printf("n");

    while (!empty(q)) {
        printf("%d ", top(q));
        pop(q);
    }
    printf("n");
    clear(q);

    return 0;
}

6.2 堆排序（线性建堆法）

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

// 线性建堆法：建堆时间 o(n)
// 堆排序：建堆时间 + 堆排序时间 = o(n) + o(n*lgn) = o(n*lgn)

#define SWAP(a, b) {
    __typeof(a) __temp = a; a = b; b = __temp;
}

// 根节点：i，左子树节点：2*i，右子树节点：2*i+1，i >= 1;
// arr：输入数组，n：数组元素的个数，ind：代表完全二叉树的节点编号
void downUpdate(int *arr, int n, int ind) {
    // ind << 1：下一层节点编号，即当前节点的左子树节点编号，其节点编号代表元素的个数
    while ((ind << 1) <= n) {
        int temp = ind, l = ind << 1, r = ind << 1 | 1; // l：下一层的左子树节点编号，r：下一层的右子树节点编号
        // 大顶堆构建（堆排序：从小到大排序），任意三元组的父节点为极大值
        if (arr[l] > arr[temp]) temp = l;
        if (r <= n &amp;&amp; arr[r] > arr[temp]) temp = r;

        // 小顶堆构建（堆排序：从大到小排序），任意三元组的父节点为极小值
        // if (arr[l] < arr[temp]) temp = l;
        // if (r <= n &amp;&amp; arr[r] < arr[temp]) temp = r;

        if (ind == temp) break; // ind == temp：三元组中的父节点为极大（小）值节点
        swap(arr[temp], arr[ind]);
        ind = temp;
    }
    return ;
}

// arr：待排序的数组，n：数组元素的个数
void heap_sort(int *arr, int n) {
    // 待排序的数组索引从0开始编号，而堆结构采取从1开始编号，故需要arr -= 1
    arr -= 1;
    // 线性建堆法 -- o(n)
    for (int i = n >> 1; i >= 1; i--) {
        downUpdate(arr, n, i);
    }
    // 堆排序的步骤：
    // 1. 将堆顶元素与堆尾元素交换
    // 2. 对前n-1元素重新建堆
    // 3. 重复1、2 两个过程，直到堆中的元素为1时停止
    for (int i = n; i > 1; i--) { // o(n * lgn)
        swap(arr[i], arr[1]);
        downUpdate(arr, i - 1, 1);
    }
    return ;
}

void output(int *arr, int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        i &amp;&amp; printf(" ");
        printf("%d", arr[i]);
    }
    printf("]n");
    return ;
}

int main() {
    srand(time(0));
    #define MAX_N 10
    int arr[MAX_N] = {0};
    for (int i = 0; i < MAX_N; i++) {
        arr[i] = rand() % 100;
    }
    output(arr, MAX_N);
    heap_sort(arr, MAX_N);
    output(arr, MAX_N);
    #undef MAX_N

    return 0;
}

代码007普通

打赏 收藏 海报 链接