算法学习5

一.堆

完全二叉树：除最后一层其他层都要填满元素，且最后一层从左到右元素必须连续，可以不填满；

1.大根堆

每一个节点都是其子节点的最大值；
如下图：

（1）从下开始向上进行

当有一个数组需要形成大根堆时，原理如下：

1. 下标当前位置开始，将当前的数与其父节点进行比较，父节点为：（i - 1）/ 2 取整数，不用四舍五入；
2. 若当前数比父节点大，则与父节点进行交互位置；
3. 交互位置后，再与当前位置的父节点进行比较，交互，不断重复该行为，直到与父节点相等或小于停止；
4. 取上一个元素继续进行；

代码：

public void heepInsert(int[] arr,int index){while(arr[index] > arr[index - 1] / 2){swap(arr,index,(index - 1) / 2);index = (index - 1) / 2;}
}

（2）从任意节点开始向下

原理：

1. 让该节点的两个子节点先进行比较，先把大的提出来；若没有或只有一个子节点就停止比较；
2. 让子节点中最大的或是一个子节点与该节点进行比较
   （1）. 若该节点大则不进行交换，并结束；
   （2）.若小则与子节点进行交换；
3. 当与子节点进行交换后，继续与交换后的子节点进行比较，直到到不需要与子节点交换为止；

代码如下：

public void heapify(int[] arr,int index,int heapSize)
{int left = index * 2 + 1;while(left < heapSize){//当下方还有孩子的时候//两个孩子中，谁的值大，把下标给largestint largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;//父和较大的孩子之间，谁的值大，把小标给largestlargest = arr[largest] > arr[index] ? largest : index;if(largest == index){break;}swap(arr,largest,index);index = largest;left = index * 2 + 1;}
}

2.堆排序

思想：
heapSize只是一个标记，方便计算位置

1. 数组中，使用heapSize表示从数组中添加到堆中的下标，该值首先从0开始；
2. 使用上面的heapInsert方法对当前堆中的数进行大根堆的比较；
3. 将数组中的下一个数添加到堆中，heapSize加1；
4. 继续进行heapInsert方法，直到数组中的所有数都添加到堆，完成大根堆比较结束；
5. 让堆中的最后一个数与第一个数进行交换；
6. 将堆中的最后一个剔除，heapSize减1；
7. 使用上面的heapify方法，从堆中的第一个数开始进行比较，直到堆中的最后一个数结束；
8. 重复步骤5到步骤7，直到heapSize减为0，则结束；

代码如下：

public void heapSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int i = 0;i < arr.length;i++){heapInsert(arr,i);}//该方法与上面的for相比要快一些，但总体时间复杂度还是一样；//for(int i = 0;i < arr.length;i++){//	heapInsert(arr,i);//}int heapSize = arr.length;swap(arr,0,--heapSize);while(heapSize > 0){heapify(arr,0,heapSize);swap(arr,0,--heapSize);}
}