电子商务网站建设实用教程教案,尚一网常德论坛,网页 网站及与之相关的概念,全网营销网站1.什么是堆
堆是一种特殊的数据结构#xff0c;它是一种二叉树#xff0c;其中每个节点都具有一个值并且满足以下两个条件#xff1a;
堆是完全二叉树#xff1a;除了最底层的叶节点外#xff0c;其他层都是满的#xff0c;并且最底层的叶节点都尽量靠左排列。堆中每个… 1.什么是堆
堆是一种特殊的数据结构它是一种二叉树其中每个节点都具有一个值并且满足以下两个条件
堆是完全二叉树除了最底层的叶节点外其他层都是满的并且最底层的叶节点都尽量靠左排列。堆中每个节点的值都大于等于或小于等于其子节点的值这取决于堆的类型。根据这一性质可以将堆分为最大堆和最小堆。
最大堆每个节点的值都大于等于其子节点的值即父节点的值大于等于子节点的值。
最小堆每个节点的值都小于等于其子节点的值即父节点的值小于等于子节点的值。
父节点i-1/2; 左孩子2*i1; 右孩子2*i2;
2.堆排序
先将待排序的数组构建成一个最大堆或最小堆然后将堆的根节点最大值或最小值与最后一个元素交换位置然后再调整堆使其满足堆的性质。重复此过程直到整个数组有序为止。
具体的步骤如下
构建最大堆每进来一个数就与它的父节点进行比较如果当前节点大于父节点交换位置。heapInsert方法将堆的根节点最大值与最后一个叶子节点交换位置然后将最后一个叶子节点从堆中移除。调整堆从根节点开始将根节点与其子节点比较选择较大的子节点与根节点交换位置然后再依次向下调整每个子树使其满足堆的性质。heapify方法重复步骤2和步骤3直到堆中只剩下一个元素。
class Solution {public int[] sortArray(int[] nums) {if(numsnull nums.length2){return nums;}int heapSize nums.length;for(int i0;iheapSize;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*index1;//当有孩子的情况下(没有左孩子一定就没有右孩子)while(left heapSize){//left1 有右孩子的情况 比较左右孩子哪个最大int largest left1 heapSize arr[left1] arr[left] ? left1 :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 temparr[a];arr[a]arr[b];arr[b]temp;}}
