大根堆
大根堆就是对于每一个元素，它的值大于等于它的孩子节点。大根堆保存在一个数组中，第 0个元素作为堆的根。那么对于下标为index的节点，他和其他节点的关系是：
- 左孩子: index * 2 + 1
- 右孩子: index * 2 + 2
- 父节点: (index - 1) / 2
建立大根堆
大根堆中的元素按照从上往下的顺序从0开始编号，按照这个编号把元素都保存在数组中。那么叶子节点一定排在数组的最后。
- 依次插入元素时，每次把元素追加到数组的最后，也就是作为一个叶子节点，这时新的节点并不符合大根堆的性质，执行
shiftup方法，逐层往上交换值。 - 删除元素时，把第
0个元素和最后一个元素交换。然后删掉最后一个元素。这时剩下的元素已经不是大根堆，执行shift down调整大根堆。
shift up
- 插入一个元素时，把元素追加到列表的最后，也就是堆的叶子节点上。然后执行shifup操作，对新元素进行从下往上的调整。
- 判断当前元素是否比父节点更大，如果是，则交换。否则就终止。
- 因为插入一个元素时，列表已经是一个大根堆，所以当出现父元素大于自己时，就没有必要继续，因为父元素的父元素值更大。
shift down
-
删除一个元素时，把该元素和列表的最后一个元素交换。然后列表的长度减一(如果用
count计数的话)。剩余的元素按照从上往下的顺序进行shiftdown操作。 -
shiftdown，如果两个孩子中存在比自己更大的元素，就和那个孩子交换值。然后这个孩子作为根，继续这个操作。
-
如下: 插入时执行shiftUp，删除时执行shiftDown
// 堆排序
class Heap{private List<Integer> data;public Heap(){this.data = new ArrayList<>();}public void insert(int value){this.data.add(value);this.shiftUp(this.data.size() - 1);}public int pop(){this.swap(0, this.data.size() - 1);int res = this.data.remove(this.data.size() - 1);this.shiftDown(0);return res;}/*** 上移，元素加入时执行* @param k*/public void shiftUp(int k){// 0 元素没有父元素// 当出现k比父元素小的时候，就没有必要继续下去，因为，父元素的父元素一定是更大的数while(k >= 1 && data.get(k) > data.get((k - 1) / 2)){swap(k, (k - 1) / 2);k = (k - 1) / 2;}}/*** 下移，调整堆时执行* @param k*/public void shiftDown(int k){// 省略了对左孩子的判断while(2 * k + 1 < data.size()){int child = 2 * k + 1;if(child + 1 < this.data.size() && this.data.get(child) < this.data.get(child + 1)){child += 1;}if(this.data.get(child) > this.data.get(k)){this.swap(k, child);}k = child;}}public void swap(int left, int right){int temp = this.data.get(left);this.data.set(left, this.data.get(right));this.data.set(right, temp);}}// main_215_数组中的第k个最大元素.Heap2 heap = handle.new Heap2();// 建立堆for(int item : list){heap.insert(item);}for(int item : list){System.out.print(heap.pop() + " ");}
heapify
- 不需要一个一个的插入元素，可以直接对原数组的所有非叶节点进行heapify，即可构成一个大根堆。
((size - 1) - 1) / 2表示最大下标减一。当然，用size/2也行，多出的几个元素都是叶子节点，都可以当成是只有一个元素的堆。
public Heap2(List<Integer> list){this.data = new ArrayList<>(list);heapify();}public void heapify(){for(int i = (data.size() - 1 - 1) / 2; i >= 0; --i){shiftDown(i);}}
就地排序
- 这里的nums数组的数据下标从0开始排，这样的话，按照如下方式计算父子节点
- 左孩子:
index * 2 + 1 - 右孩子:
index * 2 + 2 - 父节点:
(index - 1) / 2或者(length -1 -1)/2。有的算法直接用(length / 2)也不会有错，因为最右边的叶子节点都可以看成是单个的大根堆。
- 左孩子:
class Heap {public void heapSort(int [] nums){// 从第一个非叶节点开始，执行shiftdown操作int size = nums.length;// 建立一个堆// 很多携程(size-1)/2 或者 size/2都行for( int i = (size -1 - 1)/2; i >= 0; --i){shiftDown(nums, i, size);}// 从堆中取元素，取元素就是排序for (int i = size - 1; i > 0; i --){swap(nums, 0, i); // i 元素被放到0位置shiftDown(nums, 0, i); // 重新堆0位置的元素shiftdown}}/*** 对第i个元素执行下移操作。大根堆* @param nums* @param i*/public void shiftDown(int [] nums, int k, int size){// 用while 少了一次循环，避免了递归while( 2 * k + 1 < size){int child = 2 * k + 1; // 左孩子if ( child + 1 < size && nums[child+1] > nums[child])child += 1; // 右孩子if (nums[k] < nums[child]){swap(nums, child, k);}k = child; // 从被交换的孩子开始，继续往下迭代。直到到达叶子节点}}public void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}}