堆

堆

• 线性数据结构，不是非线性
• 用一维数组实现，本质为完全二叉树

遍历堆从根到叶结点

• 先从右结点开始遍历

  
  

void dfs(int d)
{
    if(2 * d > n){ //不再往下搜索
        if(d <= n){
            for(int i = 0; i < path.size(); ++i){
                if(i != path.size() - 1)
                    printf("%d ",path[i]);
                else printf("%d\n",path[i]);
            }
        }
        return;
    }
    //先走右子树
    path.push_back(keys[2 * d + 1]);
    dfs(2 * d + 1);
    path.pop_back();//回溯
    //再走左子树
    path.push_back(keys[2 * d]);
    dfs(2 * d);
    path.pop_back();//回溯
}

判断最大堆最小堆

for(int i = 2; i <= n; ++i){
       if(keys[i / 2] > keys[i]) isMin = 0;
       if(keys[i / 2] < keys[i]) isMax = 0;
    }

堆排序

基本思想：

• 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
  每次新插入的数据都与其父结点进行比较，如果插入的数比父结点大，则与父结点交换，否则一直向上交换，直到小于等于父结点，或者来到了顶端

• 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
  将n次最末尾的数提出，即可得排好序的数组，利用最大堆顶端的数一定是数组中的最大值

• 将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
  此时最大数已经来到末尾，则固定不动/提出，后面只需要对顶端的数据进行操作即可，拿顶端的数与其左右孩子较大的数进行比较——如果顶端的数大于其左右孩子较大的数，则停止；如果顶端的数小于其左右孩子较大的数，则交换，然后继续与下面的孩子进行比较

以前老是以为要递归。。。。
嗷嗷嗷，静下心写写原始堆排序也挺简单的hhh（开始做梦，然后被吊打

#include<iostream>

using namespace std;
int n;

void swap(int a,int b,int heap[]){
    int temp;
    temp=heap[a];
    heap[a]=heap[b];
    heap[b]=temp;
}

void createHeap(int heap[],int size){
    int i=size;
    while(i/2>=1){
        if(heap[i/2]<heap[i]){
            swap(i/2,i,heap);
        }
        i=i/2;
    }
}

int main(){

    cin>>n;
    int heap[1001]={0};
    for(int i=1;i<=n;i++){
        cin>>heap[i];
        createHeap(heap,i);
    }
    for(int i=1;i<=n;i++){
        cout<<heap[i]<<" ";
    }
    cout<<endl;
    for(int i=n;i>=1;i--){
        swap(1,i,heap);
        cout<<heap[i]<<" ";
        int start=1;
        while(start*2<=i-1){
            if(heap[start]<heap[start*2]){
                if(start*2+1>i-1||heap[start*2]>heap[start*2+1]){
                    swap(start*2,start,heap);
                    start=start*2;

                }
                else{
                    swap(2*start+1,start,heap);
                    start=start*2+1;
                }
            }
            else{
                if(start*2+1<=i-1&&heap[start]<heap[start*2+1]){
                    swap(start*2+1,start,heap);
                    start=start*2+1;
                }
                else break;
            }
//            cout<<"+"<<heap[start]<<"--"<<start<<endl;
        }
    }
    return 0;
}