9. 堆排序
9.1 完全二叉树
在满二叉树路上的树。
如果二叉树是完全二叉树，并且用数组表示，则:
-
位置 i 的左右孩子节点为2i+1和2i+2
-
位置 i 的父节点为（i-1)/2
9.2 堆
-
堆是完全二叉树
-
堆有大根小根之分
他的每颗子树都必须满足大根/小根堆
9.3 堆排序
1. 题目
堆排序
2. 思路
- 建立堆
先加入到应该在的地方（因为是完全二叉树，所以直接加入到数组就行），之后和父节点（(i-1)/2）比大小，比父节点大就交换，直到父节点不比他小，或者成为根。
-
删除最大值
最大的元素和size-1进行交换，而后size--
-
重复建立堆
交换后的heap[0]进行下沉，找到他合适的位置。
- 辅助数组记录每一次pop，并且返回此数组。
优先队列是堆实现的：PriorityQueue
3. 代码
新建堆：
private void newHeap(int[] arr) {
if(arr == null){
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr[i]);
}
}
添加节点进堆：
public boolean heapInsert(int val) {
if(size >= MAX_SIZE){
return false;
}
// 确定加入
size++;
int i = size-1;
heap[i] = val;
// 两个终止条件：
// 新加进来的数不比index大
// i==0 (i=0的时候 -1/2 = 0)
while(heap[i] >heap[(i-1)/2]){
swap(i,(i-1)/2);
i = (i-1)/2;
}
return true;
}
删除节点：
public int pop(){
// 第一个数删除
int max = getMax();
swap(0,size-1);
size--;
// 对于当前的堆顶，看左右孩子，谁比他大，他就下沉，直到底层
heapify(0);
return max;
}
对于某个节点下沉到合适位置：
/**
* 对于数组中的一个数，把他下沉到合适的位置
* @param index
*/
public void heapify(int index) {
int left = 2*index+1;
while(left < size){
int largestPosition = left;
// 判断右孩子
if(left+1 < size && heap[left] < heap[left+1]){
largestPosition = left+1;
}
// 判断当前节点是否需要下沉
if(heap[largestPosition] <= heap[index]){
break;
}
// 需要下沉的情况
// 交换位置和坐标信息
swap(index,largestPosition);
index = largestPosition;
left = 2*index+1;
}
}
堆排序：
public int[] heapSort(int[] arr){
int[] help = new int[arr.length];
for (int i = arr.length-1; i >= 0; i--) {
help[i] = pop();
}
return help;
}
9.4 最大线段重合问题
1. 题目
给定很多线段，每个线段都有两个数组[start，end]，表示线段开始位置和结束位置，左右都是闭区间
规定：
- 线段开始和结束位置一定是整数
- 线段重合区域的长度必须 >= 1
返回线段最多重合区域中，包含了几条线段
2. 思路
思路1暴力：取任意非整数位置，比如0.5，遍历线段的长度，如果有重叠，那么x.5一定会在里面，暴力找重合线段最多的那个，时间复杂度为O(m*n），m为线段最左最右两个的差值，n为线段条数。
思路2利用堆：
假设，有一个矩阵代表着从当前位置开始，有多少线段在这里面（也就是还没结束），也就是矩阵内存放end的值。循环遍历到了某个线段，就代表从这个线段的start开始算，这时候考虑结束位置end。如果有结束位置比当前start小，就删掉当前位置，当前数组中的元素数量就是当前线段重合的数量。
这意味着我们需要遍历所有的线段以决定是否加入到数组中O(N)，同时每次遍历线段，都需要对数组中的元素进行查看，决定是否删除。查询 + 删除后重新排序是O(N)（对于数组来说，查询常数复杂度，而删除是O(N)；对于链表反之），是N^2的复杂度。可以看看是否能够优化后半段。
我们需要删除比当前元素的左边界start小的，这就意味着，删除是从最小值开始，如何快速查找最小值呢？堆维护，每次找到并且删除一次当前最小值只需要O(logN)。
3. 代码
private static int getMaxLineNumber(int[][] input) {
Line[] lines = new Line[input.length];
// 堆内存放end元素，并且最小的放上面
PriorityQueue<Line> pq = new PriorityQueue<>(new Comparator<Line>() {
@Override
public int compare(Line o1, Line o2) {
return o1.end - o2.end;
}
});
for (int i = 0; i < input.length; i++) {
lines[i] = new Line(input[i][0],input[i][1]);
}
// 排序
Arrays.sort(lines,(Line o1, Line o2)->{
return o1.start - o2.start;
});
// Arrays.stream(lines).forEach((item)->{
// System.out.println(item.start);
// });
//
int maxSuperposition = 0;
for (int i = 0; i < lines.length; i++) {
// 加入小根堆
pq.add(lines[i]);
// 删除比他小的
while (pq.peek().end <= lines[i].start){
pq.remove();
}
// 计算当前值
int curSuperposition = pq.size();
maxSuperposition = maxSuperposition < curSuperposition? maxSuperposition = curSuperposition:maxSuperposition;
}
return maxSuperposition;
}
9.5 反向索引堆
现在的堆的问题是，想更改某一个值，只能先遍历整个堆数组找到这个位置，再将这个位置的值，进行上升（heapInsert）或者下降（heapify），如何直接找到呢？HashMap。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
/**
* 带索引的堆--可以通过索引O(1)找到元素在堆中的位置
*/
public class IndexHeap<T> {
private ArrayList<T> heap;
private HashMap<T,Integer> indexMap;
private int heapSize;
private Comparator<T> comp;
public IndexHeap(Comparator<T> c){
heap = new ArrayList<>();
indexMap = new HashMap<>();
heapSize = 0;
comp = c;
}
public boolean isEmpty(){
return heapSize == 0;
}
public int size(){
return heapSize;
}
public T peek(){
return heap.get(0);
}
public void push(T obj){
heap.add(obj);
indexMap.put(obj,heapSize);
heapInsert(heapSize);
heapSize++;
}
public T pop(){
T ans = heap.get(0);
swap(0,heapSize-1);
indexMap.remove(heapSize);
heapSize--;
heapify(0);
return ans;
}
public void remove(T obj) {
// 保存最后一条数据
T replace = heap.get(heapSize - 1);
int index = indexMap.get(obj);
// 删掉想要的元素
indexMap.remove(obj);
// 删掉最后一条数据（之前保存了不怕丢）
heap.remove(--heapSize);
// 更新记录
if (obj != replace) {
// 数组，map，堆
heap.set(index, replace);
indexMap.put(replace, index);
resign(replace);
}
}
// 更改这个值并且让他在堆中重新排序
public void resign(T obj) {
heapInsert(indexMap.get(obj));
heapify(indexMap.get(obj));
}
// 请返回堆上的所有元素
public List<T> getAllElements() {
List<T> ans = new ArrayList<>();
for (T c : heap) {
ans.add(c);
}
return ans;
}
private void heapify(int index) {
int left = index * 2 + 1;
while (left < heapSize) {
int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
if (best == index) {
break;
}
swap(best, index);
index = best;
left = index * 2 + 1;
}
}
private void heapInsert(int index) {
// 只要当前位置比父节点小，就交换 -- 默认是小
while(comp.compare(heap.get(index),heap.get((index-1)/2)) < 0){
swap(index, (index-1)/2);
index = (index-1)/2;
}
}
private void swap(int i, int j) {
T o1 = heap.get(i);
T o2 = heap.get(j);
heap.set(i,o2);
heap.set(j,o1);
indexMap.put(o2,i);
indexMap.put(o1,j);
}
}