堆和堆排序

大家好，我是星期一。今天我们讲堆，和堆排序。1.堆说到堆，首先要从二叉树说起，从二叉树到完全二叉树，再到堆。1、二叉树的每个节点最多只能有两个子树，并且有左点和右点。2、完全二叉树是一棵深度为k，有n个节点的二叉树。对于树中的节点，按从上到下，顺序从左到右编号。如果编号为i（1≤i≤n）的节点与满二叉树中相同（除了最后一层没有任何子节点，每一层上的所有节点都有两个子节点的二叉树）编号为i的节点在二叉树中有相同的位置，则称这棵二叉树为完全二叉树。通俗的说法是：叶子节点只能出现在最底层和第二底层，最底层的叶子节点集中在树的左边部分。需要注意的是，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。对于某个位置i的节点，左孩子（如果有）2i+1，右孩子（如果有）2i+2，父节点（i-1）/2（向下取整）3.堆为首先是一个完整的二叉树。同时，区分大根桩和小根桩。大根堆：每棵子树的最大值为头节点。小根堆：每棵子树的最小值为头节点。(1)对于用户依次输入的数组，如何构造成大根堆？每插入一个数，就和父节点比较，如果大于父节点，就和父节点交换，直到根节点；如果小于父节点，则立即停止比较。//对于位置i新加入的数，请将其放在数组的合适位置，使其成为大根堆privatevoidheapInsert(int[]arr,inti){//i=0orthenumberof位置i小于父节点//while包含这两个终止条件while(arr[i]>arr[(i-1)/2]){swap(arr,i,(i-1)/2);我=(我-1)/2;}}(2)获取当前数组的最大值并从堆中删除，同时保持大根堆结构publicintpop(){intans=heap[0];交换（堆，0，--heapSize）；heapify（堆，0，heapSize）；returnans;}//减少索引位置的个数，直到大孩子没有自己那么大，或者没有孩子privatevoidheapify(int[]arr,intindex,intheapSize){//左边的位置子树intleft=2*index+1;while(leftarr[left]?左+1：左；//比较左右子树中较大的一个与父节点maxIndex=arr[maxIndex]>arr[index]?maxIndex:索引；//左右子树较大的值小于父节点，停止循环if(maxIndex==index){break;节点位置来到较大的子节点index=maxIndex;//重新获取当前节点的左子树left=2*index+1;}}4.PriorityQueue底层是用堆实现的，默认是一个小根堆。中间加一个数，时间复杂度O(logN)heapify，对已经在堆结构中的数加一个数，时间复杂度O(logN)2.堆排序1.将整个数组调整为大根堆，则此时0位置的数为最大值。2.将位置0的数与数组的最大位置交换。此时最大值在最后排序的位置。3.数组中调整范围的个数减一，循环执行1、2步，直到数组为空publicstaticvoidheapSort(int[]arr){if(arr==null||arr.length<2){返回;}//将整个数组调整为一个大的根堆，O(NlogN)for(inti=0;i0){//将交换后的数下沉到位置0，即再次将当前数组调整为大根堆(arr,0,heapSize);//交换位置0的个数和数组的最大位置swap(arr,0,--heapSize);}}4.复杂度(1)时间复杂度：O(N*logN)(2)额外空间复杂度：O(1)