文章目录

• 学习目标：
• 学习内容：
• 学习时间：
• 学习产出：
• • 1.什么是堆结构以及堆排序？
  • 2.构造堆 heapInsert
  • 3.构造堆 heapify
  • 4.堆排序算法
  • 5.用时间复杂度O(N)来构造大根堆
  • 6.Java API 实现堆
  • 7.最大移动距离数组排序-堆扩展

学习目标：

我会持续更新我独特的算法思路，希望能给大家带来不一样的思维拓展！
如果大家感觉有帮助的话，欢迎点赞关注支持哦！
你们的鼓励是我坚持下去的动力！
！！！

学习内容：

堆排序
牛客网链接

学习时间：

2022.4.7-8

学习产出：

1.什么是堆结构以及堆排序？

2.构造堆 heapInsert

3.构造堆 heapify

4.堆排序算法

using System;class test{    static void Main(){ int count=Convert.ToInt32( Console.ReadLine()); string[] putin=Console.ReadLine().Split(' '); int[] arr=new int[count]; for(int i=0;i<count;i++){     arr[i]=Convert.ToInt32(putin[i]); }  //O(NlogN) for(int i=0;i<count;i++){     heapInsert(arr, i); }  //O(N) //for(int i=count-1;i>=0;i--){ //    heapify(arr, i, count); //}  int heapSize=count; //我们现在已经构造好了大根堆 Swap(arr,0,--heapSize); while(heapSize>0){     heapify(arr, 0, heapSize);     Swap(arr, 0, --heapSize); }  for(int i=0;i<count;i++){     Console.Write(arr[i]+" "); }    } //小元素下沉，大元素上升，构造大根堆    static void heapify(int[] arr,int index,int heapSize){ int left=index*2+1; while(left<heapSize){//没有越界     //拿到左子树或者右子树中较大的索引     int larIndex=left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;      //拿到父左右，三个节点中较大的位置     larIndex=arr[index]>arr[larIndex]?index:larIndex;     //如果父节点最大，则不需要下沉     if(larIndex==index)break;   //交换，让父节点下沉，较大的作为父节点     Swap(arr,larIndex,index);     index=larIndex;     left=index*2+1; }    }    static void heapInsert(int[] arr,int index){ while(arr[index]>arr[(index-1)/2]){     Swap(arr, index, (index-1)/2);     index=(index-1)/2; }    }    static void Swap(int[] arr,int index1,int index2){ int temp=arr[index1]; arr[index1]=arr[index2]; arr[index2]=temp;    }}

5.用时间复杂度O(N)来构造大根堆

6.Java API 实现堆

7.最大移动距离数组排序-堆扩展

题目要求的是排序这个数组的时候，每个元素移动不会超过k个位置。
那么，我们可以将数组前k+1个数，构造成一个堆，这个堆的排序是严格符合题目要求的。
为什么？
因为就算是最后一个位置，索引为k的这个元素，移动到0，也只移动了k个位置，相当于说，在排序好的这个k个元素的堆，每个元素都满足最多只移动k个位置。
那么久不断往后构造堆，不断popMax即可！