838. 堆排序

2021年09月15日 阅读数:1
这篇文章主要向大家介绍838. 堆排序,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目传送门ios

1、手写一个堆(小根堆)

前三个操做就是\(STL\)里堆支持的操做c++

一、插入一个数

    heap[++size]=x; //在一维数组最后一个位置填充x
    up(size);       //将最后一个元素不断上移

二、求最小值

    heap[1]

三、删除最小值

    heap[1]=heap[size--]; //就是把尾部最后一个元素替换掉头元素,而后size--
    down(1);              //而后再down(1)就好了

如下两个操做STL没法实现或者说没法直接实现数组

四、删除任意一个元素

    heap[k]=heap[size--];
    down(k);
    up(k);   //其实只能执行一个,由于大了向下走。小了向上走嘛

五、修改任意一个元素

    heap[k]=x;
    down(k);
    up(k);

堆是一个彻底二叉树。除了最后一层结点之外,上面的每一层都是满的。最后一层的结点是从左到右排布的。
小根堆:每个点都是小于左右儿子的,因此根节点就是树中最小值.或者叫小顶堆
存储方式:全新的存储方式,用一维数组来存。由于是彻底二叉树,全部数据的下标是有规则能够找到的。
\(x\)---左儿子\(2x\)---右儿子\(2x+1\)优化

下标是从\(1\)开始的,从\(0\)开始不方便,由于\(2x\)仍是本身无法玩spa

两个基本操做,这两个操做结合起来就能完成上面五个操做。
\(down(x)\) ---> 向下调整
\(up(x)\) ---> 向上调整code

2、完整代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int heap[N];
int sz;

/**
 * 功能:向下移动
 * @param u
 */
void down(int u) {
    int t = u;
    if (u * 2 <= sz && heap[u * 2] < heap[t])t = u * 2;
    if (u * 2 + 1 <= sz && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
    if (u != t) {
        swap(heap[u], heap[t]);
        down(t);
    }
}
/**
 * 功能:向上移动
 * @param u
 */
void up(int u) {
    //若是父节点存在,而且父节点值大于u节点值
    while (u / 2 && heap[u / 2] > heap[u]) {
        swap(heap[u / 2], heap[u]);
        u /= 2;
    }
}


int main() {
    //读入优化
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> heap[i];
    sz = n;

    //如何初始化堆
    //这是一个小技巧,建堆的技巧O(N),其实也能够是int i=n;i>0;i--,但最后一层再down没有意义,省略
    for (int i = n / 2; i; i--)down(i);

    //遍历提取出来
    while (m--) {
        printf("%d ", heap[1]);
        //删除堆顶
        heap[1] = heap[sz--];
        //再down一次
        down(1);
    }
    return 0;
}

3、图解说明