[数据结构与算法]完全二叉树应用之堆排序算法

完全二叉树应用之堆排序算法

原理

完全二叉树是严格按照从上到下，从左向右排列的二叉树

步骤：

1、根据给定的关键词创建一个堆
2、输出堆顶的元素（如果是最大值则为最大堆，最小值则为最小堆）
3、调整余下元素，使其成为一个新堆（从 size/2 开始调整 即倒数第二次最后一个根节点开始调整）
4、重复（2）（3），直到输出n个元素，得到一个有序数列

/*
 * @Description: 最小堆排序算法
 * @Version: 0.1
 * @Autor: Wyz
 * @Date: 2021-09-09 11:29:53
 */
#include <iostream>
#include <vector>
using namespace std;

// struct BtreeNode{
//     int data;
//     int left;
//     int right;
//     int parent;
// };

// 完全二叉树按数组形式排序，第 i 位的左子树(2*i+1)， 右子树(2*i+2)

class Solution{
public:
    void swap(int& a, int& b){
        int temp = b;
        b = a;
        a = temp;
    }

    /* 堆调整 */
    void heapify(vector<int>& tree ,int size, int i){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int parent = (i - 1) / 2;

        // 左右子树不存在 
        if(left > size )
            return ;
        // 只存在左子树
        else if(left <= size && right > size){
            if(tree[i] > tree[left]){
                swap(tree[i], tree[left]);
            }
            return ;
        }
        
        // 既有左子树又有右子树
        else{
            // 找这三个的最小值交换[i] 与 [index]
            int min = i;
            if(tree[min] > tree[left])
                min = left;
            if(tree[min] > tree[right])
                min = right;
            swap(tree[i], tree[min]);
        }
        return ;
    }
    
    /* 创建一个堆 */
    vector<int>& creat_heap(vector<int>& tree){
        int size = tree.size() - 1 ;
        int n = size / 2;
        while(n >= 0){
            heapify(tree,size,n);
            n--;
        }
        return tree;
    }

    vector<int> min_heap_sort(vector<int>& tree){
        vector<int> ans;
        while(tree.size()-1 > 0){
            vector<int> res = creat_heap(tree);
            ans.push_back(res.front());
            tree.erase(tree.begin());
        }
        // 最后一个元素直接加入就行了
        ans.push_back(*tree.begin());
        return ans;
    }
};

int main(){
    vector<int> tree{49,97,13,38,27,49,76,65,44,54,33};
    Solution sl;
    vector<int> res = sl.min_heap_sort(tree);
    for(auto i : res)
        std::cout << i << " ";
    std::cout << std::endl;
    return 0;
}