1.什么是堆
堆是一种特殊的数据结构,它是一种二叉树,其中每个节点都具有一个值并且满足以下两个条件:
- 堆是完全二叉树:除了最底层的叶节点外,其他层都是满的,并且最底层的叶节点都尽量靠左排列。
- 堆中每个节点的值都大于等于或小于等于其子节点的值,这取决于堆的类型。根据这一性质,可以将堆分为最大堆和最小堆。
最大堆:每个节点的值都大于等于其子节点的值,即父节点的值大于等于子节点的值。
最小堆:每个节点的值都小于等于其子节点的值,即父节点的值小于等于子节点的值。
父节点:(i-1)/2; 左孩子2*i+1; 右孩子:2*i+2;
2.堆排序
先将待排序的数组构建成一个最大堆(或最小堆),然后将堆的根节点(最大值或最小值)与最后一个元素交换位置,然后再调整堆,使其满足堆的性质。重复此过程,直到整个数组有序为止。
具体的步骤如下:
- 构建最大堆:每进来一个数,就与它的父节点进行比较,如果当前节点大于父节点,交换位置。(heapInsert方法)
- 将堆的根节点(最大值)与最后一个叶子节点交换位置,然后将最后一个叶子节点从堆中移除。
- 调整堆:从根节点开始,将根节点与其子节点比较,选择较大的子节点与根节点交换位置,然后再依次向下调整每个子树,使其满足堆的性质。(heapify方法)
- 重复步骤2和步骤3,直到堆中只剩下一个元素。
class Solution {
public int[] sortArray(int[] nums) {
if(nums==null && nums.length<2){
return nums;
}
int heapSize =nums.length;
for(int i=0;i<heapSize;i++){
heapInsert(nums,i);
}
swap(nums,0,--heapSize);
while(heapSize >0){
heapify(nums,0,heapSize);
swap(nums,0,--heapSize);
}
return nums;
}
//建堆
public void heapInsert(int[] arr,int index){
// 如果当前节点大于父节点,交换位置,然后继续向上迭代
while(arr[index]> arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index =(index-1)/2;
}
}
public void heapify(int[] arr, int index, int heapSize){
//左孩子
int left = 2*index+1;
//当有孩子的情况下(没有左孩子一定就没有右孩子)
while(left < heapSize){
//left+1 有右孩子的情况 ,比较左右孩子哪个最大
int largest = left+1< heapSize && arr[left+1] >arr[left] ? left+1 :left;
//判断当前节点和子节点的数谁大
largest = arr[largest] >arr[index] ? largest :index;
//如果最大数已经是当前数了,结束,否则与子节点交换
if(largest == index){
break;
}
swap(arr,largest,index);
index =largest;
left = 2*index +1;
}
}
public void swap(int[] arr, int a,int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}