PAT甲级备考——堆

• 题目
• • 【1147】判断最大最小堆、递归后序遍历
  • 【1098】heap sort 堆排序、判断是否是插入排序
  • 堆排序

PAT (Advanced Level) Practice

【1147】判断最大最小堆、递归后序遍历
【1155】Heap Paths  [深搜回溯，堆]（）
【1098】heap sort 堆排序、判断是否是插入排序

#include
#include
using namespace std;
vector tree;
int M, N;
void postOrder(int index){ // 后序遍历
    if(index > N) return;
    postOrder(index*2);
    postOrder(index*2+1);
    printf("%d%s", tree[index], index==1?"n":" ");
}
int main(){
    cin>>M>>N;
    tree.resize(N+1);
    while(M--){
        // 判断是否是最小堆（min heap）或者最大堆（max heap）或者不是堆（not heap）
        // 最小堆：父节点小于等于子节点
        // 最大堆：父节点大于等于子节点
        bool isMax = true, isMin = true;
        for(int i=1; i<=N; i++){
            scanf("%d", &tree[i]);
            if(i>=2){
                if(tree[i]tree[i/2]) isMax = false; // 如果父节点比子节点小，则不是最大堆
            }
        }
        if(!isMax && !isMin){
            printf("Not Heapn");
        }else{
            printf(isMax==true ? "Max Heapn":"Min Heapn");
        }
        postOrder(1); // 递归后序遍历
    }
}

堆：完全二叉树
最大堆：每个结点的值都大于等于其左右孩子的节点值 arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
最小堆：每个结点的值都小于等于其左右孩子的节点值 arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序：

   构建初始堆 + 交换堆顶元素和末尾元素并重建堆

再简单总结下堆排序的基本思路：
　　a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
图解排序算法(三)之堆排序 - dreamcatcher-cx - 博客园 (cnblogs.com)

#include
#include
#include
using namespace std;
int n;
void adjust_heap(vector &part, int i, int length){
    int temp = part[i]; // temp为当前节点i的值
    for(int k=i*2+1; k // 先遍历当前节点i的左子节点
        if(k+1
    
    cin>>n;
    vector init(n);
    vector part(n);
    for(int i=0; i
        sort(part.begin(), part.begin()+index+1);
    }else{
        // 堆排序
        // 找到区分点i
        int i, temp = part[n-1];
        for(i=n-2; i>=0; i--){
            if(part[i]+1!=temp) break;
            else temp = part[i];
        }
        // swap 0 and i
        swap(part[0], part[i]);
        // adjust heap，在下标值为0到i-1的子序列上调整堆
        adjust_heap(part, 0, i);
    }
    for(int i=0; i 
堆排序 
#include
#include
#include
using namespace std;

void adjust_heap(vector &arr, int i, int length){
    int temp = arr[i]; // temp为暂存堆顶元素
    int k=i*2+1; // k置为左节点
    while(k // 节点下标不超过最大
        if(k+1
    
    vector arr = {9,8,7,6,5,4,3,2,1,0};
    int n = arr.size();
    
    // 注意堆是完全二叉树 ，节点i的左节点为（2*i+1），右节点为（2*i+2）, 若i从0开始
    
    // 1. 先从第一个非叶子节点开始遍历，构建堆， 从左至右，从下至上
    for(int i=n/2-1; i>=0; i--){
        adjust_heap(arr, i, n);
    }
    // 2. 交换堆顶和最后一个元素，并重新对堆进行调整
    for(int j=n-1; j>=0; j--){
        swap(arr[0], arr[j]);
        adjust_heap(arr, 0, j);
    }
    // 3. 输出
    for(int i=0; i
        printf("%d%s", arr[i], i==n-1?"n":" ");
    }
}