[数据结构与算法]2021-08-13

2.完全二叉树

（1）简介

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

树的储存方式分为顺序储存和链式储存，顺序储存一般使用数组实现，链式储存一般使用链表实现。由于一般的树由于数据关系1使用顺序储存时会造成数组的浪费，但是完全二叉树却无需考虑这些。

（2） 堆

1》概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2》性质

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

  3》堆的操作

  down操作

  接下来通过一道题来理解一下堆的操作

  输入一个长度为 nn 的整数数列，从小到大输出前 mm 小的数。

  输入格式

  第一行包含整数 nn 和 mm。

  第二行包含 nn 个整数，表示整数数列。

  输出格式

  共一行，包含 mm 个整数，表示整数数列中前 mm 小的数。

  数据范围

  1≤m≤n≤1051≤m≤n≤105， 1≤数列中元素≤1091≤数列中元素≤109

  输入样例：

  5 3
  4 5 1 3 2

  输出样例：

  1 2 3

 #include<algorithm>
 #include<iostream>
 using namespace std;
 const int N=1e5+7;
 int a[N];
 int size;
 void down(int i){
    int t=i;
    if(i*2<=size&&a[i*2]<a[t])t=i*2;
    if(i*2+1<=size&&a[i*2+1]<a[t])t=i*2+1;//判断左右儿子是否存在，并且找到三个点之间最小的那个；
    if(t!=i){//如果t!=i可说明最小的那个点不是i
        swap(a[i],a[t]);
        down(t);
    } ?
 }
 int main(){
 ? ? int n,m;
 ? ? scanf("%d%d",&n,&m);
 ? ? size=n;
 ? ? for(int i=1;i<=n;i++){
 ? ?    scanf("%d",&a[i]);
     }
     for(int i=n/2;i;i--){
        down(i);
     }
     for(int i=1;i<=m;i++){
     ? ? printf("%d ",a[1]);
         a[1]=a[size];
         size--;//将头结点删除
         down(1); 
     }
     
 }