PAT甲级备考——堆

PAT甲级备考——堆

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

题目

PAT (Advanced Level) Practice

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

【1147】判断最大最小堆、递归后序遍历

#include
#include
using namespace std;
vector<int> 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]) isMin = false; // 如果父节点比子节点大，则不是最小堆；
                else if(tree[i]>tree[i/2]) isMax = false; // 如果父节点比子节点小，则不是最大堆
            }
        }
        if(!isMax && !isMin){
            printf("Not Heap\n");
        }else{
            printf(isMax==true ? "Max Heap\n":"Min Heap\n");
        }
        postOrder(1); // 递归后序遍历
    }
}

【1098】heap sort 堆排序、判断是否是插入排序

堆：完全二叉树
最大堆：每个结点的值都大于等于其左右孩子的节点值 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<int> &part, int i, int length){
    int temp = part[i]; // temp为当前节点i的值
    for(int k=i*2+1; k<length; k=k*2+1){ // 先遍历当前节点i的左子节点
        if(k+1<length && part[k]<part[k+1]) // 如果存在右子节点，且右子节点的值大于左子节点，那就先遍历右子节点
            k++;
        if(part[k]<=temp) break; // 如果i子节点的值都小于i节点的值，那么符合堆的特征，退出
        swap(part[i], part[k]); // 如果不符合，则交换i和i的子节点k的值
        i = k; // 接着向下遍历
    }
}


int main(){
    /*
        1. 输入init顺序，和partial排序后的顺序
    */
    cin>>n;
    vector<int> init(n);
    vector<int> part(n);
    for(int i=0; i<n; i++) scanf("%d", &init[i]);
    for(int i=0; i<n; i++) scanf("%d", &part[i]);
    
    /*
        2. 判断是否是insertion插入排序
        3 1 2 8 7 5 9 4 6 0
        1 2 3 7 8 5 9 4 6 0
        插入排序中前半部分按照从小到大的顺序排列，后半部分part与init相同，如果符合以上两个特征则是插入排序
    */
    int p = 1;
    while(p<n && part[p-1]<=part[p]) p++;
    int index = p;
    while(p<n && init[p]==part[p]) p++;
    
    printf("%s\n", (p==n)?"Insertion Sort":"Heap Sort");
    
    /*
        3.分情况insertion和heap排序，在part的基础上再迭代一步，并输出结果
    */
    if(p==n){
        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<n; i++) printf("%d%s", part[i], i==n-1?"\n":" ");
}

堆排序

#include
#include
#include
using namespace std;
/*
    堆排序
*/
void adjust_heap(vector<int> &arr, int i, int length){
    int temp = arr[i]; // temp为暂存堆顶元素
    int k=i*2+1; // k置为左节点
    while(k<length){ // 节点下标不超过最大
        if(k+1<length && arr[k]<arr[k+1]) k++; // 如果存在右节点，且右节点的值大于左节点，则k置为右节点
        if(arr[k] <= temp) break; // 如果子节点的值小于等于堆顶元素，符合堆的特性，退出
        swap(arr[k], arr[i]); // 否则交换i和子节点k
        i = k; // 置i为k
        k = k*2+1; // k为子节点继续遍历
    }
}
int main(){
    
    vector<int> 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<n; i++){
        printf("%d%s", arr[i], i==n-1?"\n":" ");
    }
}