[1]# 堆排序
基本思路
- 借助平衡二叉树性质
- 元素排列顺序的特殊性 进而形成 大顶堆和小顶堆
- 逻辑思路 参考数据结构:堆 - 知乎 (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的数值是比较小的