2022年1月

堆排序

基本思路

  1. 借助平衡二叉树性质
  2. 元素排列顺序的特殊性 进而形成 大顶堆和小顶堆
  3. 逻辑思路 参考数据结构:堆 - 知乎 (zhihu.com)

简单代码实现

  • 迭代生成

    void maxHeap(vector<int>&arr,int start,int end){
        int dad=start;  //父节点从0 开始
        int son=dad*2+1;
        while(son<=end){
            if(son+1<=end&&arr[son]<arr[son+1])++son;
            if(arr[dad]>arr[son]) return;
            else{
                swap(arr[dad],arr[son]);
                dad=son;
                son=dad*2+1;
            }
        }
    }
  • 递归生成

    def maxHeap01(self,start, end):
            dad=start
            son=dad*2+1
            while son<=end:
                if son+1 <=end and self.ls[son]<self.ls[son+1]:son+=1
                if self.ls[dad]>self.ls[son]:return
                else:
                    self.ls[dad],self.ls[son]=self.ls[son],self.ls[dad]
                    dad=son
                    son=dad*2+1#dad的数值是比较小的

完整代码地址

地址