Catshao

用户名：Catshao

访问量：28829

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

【小灰】树状数组动画详解
浏览：176

vector、deque、list的速度和内存的比较
浏览：555

Dotcpp编程2021年七月月赛题面
浏览：740

你可能喜欢

【小白向】二叉堆vector实现详解

　　作者: Catshao　　　　发表时间：2021-01-30 22:52:25 浏览：469　|　评论：1　

原题链接：数据结构-堆排序

[TOC]

# Part -1 前置算法

在阅读这篇题解之前，你需要明白完全二叉树的概念，[百度一下](https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin)

# Part 1 概述

二叉堆是一种寻找最大值最小值十分**高效**的数据结构。

普通二叉堆主要分为两种：
* 小根堆
* 大根堆

**特性**：二叉堆的每一个节点都比它的子节点大（大根堆）或小（小根堆）。

**时间复杂度**：插入删除为$$\log n$$，去最大最小为常数。

为了保持这个特性，我们需要在插入删除时互换节点。

### 操作

#### 插入（小根堆）

1. 将节点插入到最后一个位置。
2. 与双亲节点比较，如果比上一个节点小就互换。
3. 重复2，直到双亲节点比节点小，或者节点位于根节点。

![动画](http://cat-shao.gitee.io/mypic/heap-insert.gif)

#### 删除（小根堆）

删除默认都是删除堆的根节点。

1. 删除根节点。
2. 使用最后一个节点来补根节点的位置。
3. 与子节点互换调整，保持特性。应该选择左右节点中小的来换。

![动画](http://cat-shao.gitee.io/mypic/heap-pop-new.gif)

### 实现

在实现之前，我们来复习下完全二叉树的性质：

如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) 有: 
- 如果`i = 1`, 则结点i是二叉树的根, 无双亲;如果i>1, 则其双亲节点是结点**i/2**
- 如果`2i>n`, 则结点i无左孩子, 否则其左孩子是结点**2i**; 
- 如果`2i+1>n`, 则结点i无右孩子, 否则其右孩子是结点**2i+1**.

由于我们每一次插入和删除，都是在堆的最后一个节点的位置调整的，所以整个堆可以填充整个数据（不会出现稀疏状况），使用完全二叉树的特性可以快速定位双亲节点和子节点，所以，**使用vector不会浪费空间**

但是vector互换节点的速度并不快，可以考虑用一个临时变量存储，直到找到一个合适的节点，**只进行一次互换**（见我的代码）

#### 我的实现 （小根堆）
```cpp
//
// Created by Cat-shao on 2021/1/15.
// 小根堆模板
#include <vector>
using namespace std;
template<typename T>
class heap // 小根堆模板
{
public:
    int length;
    vector<T> tree;
    heap () {
        clear();
    }
    bool empty() {
        return length <= 0;
    }
    void clear() {
        tree.clear();
        tree.resize(1);
        length = 0;
    }
    void push(const T &x) {
        if (length == tree.size() - 1) {
            tree.resize(tree.size() * 2);
        }
        int index = ++ length;
        for (; index > 1 && x < tree[index / 2]; index /= 2) { // n / 2为父节点，n/=2即为n到父节点，n > 1为n不是根节点
            tree[index] = tree[index / 2]; // 将父节点的值付给自己
        }
        tree[index] = x; // x 上去
    }
    void pop() {
        if (empty()) {
            return;
        }
        tree[1] = tree[length --];
        percolateDown(1);
    }
    void percolateDown(int index) {
        T x = tree[index];
        int childIndex;
        for (; index * 2 <= length; index = childIndex) {
            childIndex = 2 * index; // 子节点 = 2k 或 2k+1
            if (childIndex != length && tree[childIndex + 1] < tree[childIndex]) { // 右节点合法并且比左节点小
                childIndex ++;
            }
            if (tree[childIndex] < x) {
                tree[index] = tree[childIndex]; // 父节点、子节点互换
            } else {
                break;
            }
        }
        tree[index] = x;
    }
    int size() {
        return length;
    }
    T top() {
        return tree[1];
    }
    T front() {
        return tree[1];
    }
};
```

参考：
* [小灰的文章](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195207&idx=2&sn=12689c6c1a92e7ec3cce4d423019ec2a&chksm=8c99f91dbbee700b8e760d06b27582037ab0713295dacf2b5a7a7f954c0032fe860aa0bf8b74&scene=21#wechat_redirect)
* [可视化](https://www.cs.usfca.edu/~galles/visualization/Heap.html)

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

一个努力成长的程序媛

好厉害啊！想知道你上面的视频是什么软件做的呀？

2022-03-14 13:52:46

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言训练-求素数问题（C语言代码）

弟弟的作业（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

【小白向】二叉堆vector实现详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

求组合数（C语言代码）

【简单计算】（C语言代码）

【计算球体积】（C语言代码）

最小公倍数（C语言代码）

1024题解

有关字符，字符串的输入输出函数说明

局部变量作函数返回值的问题

1050题解（结构体数组与结构体指针的使用）

永远的丰碑（C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

C语言训练-求素数问题 （C语言代码）

弟弟的作业 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

【小白向】二叉堆vector实现详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

求组合数 （C语言代码）

【简单计算】 （C语言代码）

【计算球体积】 （C语言代码）

最小公倍数 （C语言代码）

1024题解

有关字符，字符串的输入输出函数说明

局部变量作函数返回值的问题

1050题解（结构体数组与结构体指针的使用）

永远的丰碑 （C语言代码）

C二级辅导-公约公倍（C语言代码）

C语言训练-求素数问题（C语言代码）

弟弟的作业（C++代码）

　　评论区

求组合数（C语言代码）

【简单计算】（C语言代码）

【计算球体积】（C语言代码）

最小公倍数（C语言代码）

永远的丰碑（C语言代码）