06、算法与数据结构 - 实战：堆与堆排序
堆结构
一种以数组模拟二叉树的结构
分大顶堆和小顶堆
如果是大顶堆，则父节点比两个孩子节点大，但是孩子节点间不做比较
小顶堆则是父节点比两个孩子节点小
以数组下标0位置作为根节点，1作为左孩子，2最为右孩子，后面的以此类推
则有下标换算公式：
left：2 * i + 1
rifht：2 * i + 2
parent：(i - 1) / 2
也可以以数组下标1作为根节点，则下标换算公式是：
left：2 * i
rifht：2 * i + 1
parent：i / 2
插入一个节点时，先插入到尾部（size位置），然后在size++，然后做向上调整
弹出一个节点时，先把头结点与尾部节点交换，然后size–，然后头结点做向下调整
/**
* 堆结构（大根堆）
*/
public class Heap01 {
private int[] arr;
private int heapSize;
public Heap01(int size) {
arr = new int[size];
heapSize = 0;
}
public void push(int num) {
if (heapSize == arr.length) throw new RuntimeException("heap is full");
arr[heapSize] = num;
//堆调整：上浮
floatUp(arr, heapSize++);
}
private void floatUp(int[] arr, int index) {
//堆调整：上浮
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private void sink(int[] arr, int heapSize) {
//堆调整：下沉
int index = 0;
int l = index * 2 + 1;
int r;
int bigSon;
//还有左孩子，就继续比较，没有左孩子，就不再比较了
while (l < heapSize) {
r = index * 2 + 2;
bigSon = r < heapSize && arr[r] > arr[l] ? r : l;
if (arr[bigSon] <= arr[index]) break;
swap(arr, index, bigSon);
index = bigSon;
l = index * 2 + 1;
}
}
public int pop() {
if (heapSize == 0) throw new RuntimeException("heap is empty");
int res = arr[0];
swap(arr, 0, --heapSize);
sink(arr, heapSize);
return res;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
堆排序
1、 先遍数组，每个数做向上调整，相当于入堆，建立堆结构；
2、 然后每次把堆顶数与尾部数（size-1位置）交换，size–，换到尾部的数是最大的，不再动了；
3、 然后当前堆顶做向下调整，调整好后，继续堆顶与尾部数交换，依次类推；
/**
* 堆排序
*/
public class Heap02 {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
//模拟从数组放入元素，调整为大顶堆
for (int i = 0; i < arr.length; i++) {
floatUp(arr, i);
}
int heapSize = arr.length;
while (true) {
swap(arr, 0, --heapSize);
if (heapSize == 0) break;
sink(arr, heapSize);
}
}
private static void floatUp(int[] arr, int index) {
//堆调整：上浮
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private static void sink(int[] arr, int heapSize) {
//堆调整：下沉
int index = 0;
int l = index * 2 + 1;
int r;
int bigSon;
//还有左孩子，就继续比较，没有左孩子，就不再比较了
while (l < heapSize) {
r = index * 2 + 2;
bigSon = r < heapSize && arr[r] > arr[l] ? r : l;
if (arr[bigSon] <= arr[index]) break;
swap(arr, index, bigSon);
index = bigSon;
l = index * 2 + 1;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
从上往下建堆复杂度是O(N * logN)，建堆的过程可以优化，改为从下往上建堆，就是数组从后往前做向下调整，建堆的过程可以优化为O(N)
几乎有序的数组排序问题
一个数组几乎有序，数组在排序完之后，每一个数距离原位置移动的距离不超过k
给定一个数组，与k，对数组进行排序
先建一个k+1大小的小根堆，把前k+1个数入堆，然后弹出一个数放0位置，k+1位置的数入堆，再弹出一个数放1位置，一次类推，从堆弹出一个数放好，再把1一个数入堆，最后没数入堆了，就一次弹出直到弹空。时间复杂度O(N * logK)。
/**
* 几乎有序的数组排序问题：
* 一个数组几乎有序，数组在排序完之后，每一个数距离原位置移动的距离不超过k
* 给定一个数组，与k，对数组进行排序
*/
public class Heap03 {
public static void sort(int[] arr, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0;
for (; index <= Math.min(arr.length - 1, k); index++) {
heap.add(arr[index]);
}
int i = 0;
for (; index < arr.length; index++) {
arr[i++] = heap.poll();
heap.add(arr[index]);
}
while (!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
}
线段最大重合问题
给定很多线段，每个线段都有两个数[start, end]
表示线段的开始位置和结束位置，左闭右闭区间
规定： 1)线段的开始位置和结束位置都是整数值
2)线段的重合区域必须>=1
返回线段最多重合区域中，包含了几条线段
1、 先把选的按开始位置从小打到排序；
2、 建立一个小根堆，由于存放线段的结束位置；
3、 遍历每一条线段，把堆中小于当前线段的结束位置弹出，然后把当前线段的结束位置放入堆中；
4、 结算堆中的线段数，与返回值pk一下，抓住最大值；
/**
* 线段最大重合问题
* 给定很多线段，每个线段都有两个数[start, end]
* 表示线段的开始位置和结束位置，左闭右闭区间
* 规定：
* 1)线段的开始位置和结束位置都是整数值
* 2)线段的重合区域必须>=1
* 返回线段最多重合区域中，包含了几条线段
* Created by huangjunyi on 2022/11/20.
*/
public class Heap04 {
private static class Line {
int start;
int end;
public Line(int start, int end) {
this.start = start;
this.end = end;
}
}
public static int maxCover(int[][] m) {
if (m == null || m.length < 0) return 0;
int N = m.length;
// 线段数组
Line[] lines = new Line[N];
for (int i = 0; i < m.length; i++) {
lines[i] = new Line(m[i][0], m[i][1]);
}
// 按线段的开始位置从小到大排序
Arrays.sort(lines, (line1, line2) -> line1.start - line2.start);
// 小根堆，存放线段的结束位置
PriorityQueue<Integer> heap = new PriorityQueue<>();
int res = 0;
for (int i = 0; i < lines.length; i++) {
Line line = lines[i];
// 把小于等于当前线段开始位置的结束位置弹出
while (!heap.isEmpty() && heap.peek() <= line.start) heap.poll();
heap.add(line.end);
// 抓住最大值
res = Math.max(res, heap.size());
}
return res;
}
}
可动态调整的堆
PriorityQueue不支持修改了堆中元素的值后，动态调整堆结构，如果要支持这种功能的堆，只能自己改写堆结构
1、 需要一个Map作为反向索引表，记录元素到堆中位置的映射；
2、 元素入堆、出堆，反向索引表要同步更新；
3、 堆中两元素交换位置，反向索引表也要同步更新（可以封装到swap方法中）；
4、 定一个方法，用于接收外部通知堆中某个元素已经被修改了，要做堆调整；
/**
* 可动态调整的堆：
* 当堆中的元素的值发生变化时，可以重新调整该元素在堆中的位置
*/
public class Heap05<T> {
private List<T> arr; // 堆容器
private Map<T, Integer> indexMap; // 反向索引表
private int heapSize; // 堆大小
private Comparator<T> comparator; // 比较器
public Heap05(Comparator<T> comparator) {
this.comparator = comparator;
this.arr = new ArrayList<>();
indexMap = new HashMap<>();
this.heapSize = 0;
}
public void push(T t) {
int size = arr.size();
arr.add(t); // 添加到尾部
indexMap.put(t, size); // 记录反向索引
floatUp(size); // 向上调整
heapSize++;
}
public T pop() {
T res = arr.get(0); // 弹出的元素
swap(0, heapSize - 1); // 与尾部交换
arr.remove(heapSize - 1); // 删掉要弹出的元素
indexMap.remove(res); // 删除反向索引
sink(0, --heapSize); // 交换到头部的元素，做向下调整
return res;
}
public void remove(T obj) {
T replace = arr.get(heapSize - 1); // 尾部元素
Integer index = indexMap.get(obj); // 要删除元素的位置
indexMap.remove(obj);
heapSize--;
if (obj == replace) return; // 如果要删除的元素，就是尾部元素，删除就走
arr.set(index, replace); // 尾部元素替换到删除位置
indexMap.put(replace, index); // 更新反向索引
resign(replace); // 堆调整
}
public void resign(T t) {
//元素的值发生变化，重新调整该元素在堆中的位置
int index = indexMap.get(t);
floatUp(index);
sink(index, heapSize);
}
public List<T> getALL() {
return new ArrayList<>(this.arr);
}
public boolean contains(T t) {
return indexMap.containsKey(t);
}
public int size() {
return heapSize;
}
public T peek() {
return arr.get(0);
}
private void floatUp(int index) {
//堆调整：上浮
//while (arr[index] > arr[(index - 1) / 2]) {
while (comparator.compare(arr.get(index), arr.get((index - 1) / 2)) > 0) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private void sink(int index, int heapSize) {
//堆调整：下沉
int l = index * 2 + 1;
int r;
int bigSon;
//还有左孩子，就继续比较，没有左孩子，就不再比较了
while (l < heapSize) {
r = index * 2 + 2;
//bigSon = r < heapSize && arr[r] > arr[l] ? r : l;
bigSon = r < heapSize && comparator.compare(arr.get(r), arr.get(l)) > 0 ? r : l;
//if (arr[bigSon] <= arr[index]) break;
if (comparator.compare(arr.get(bigSon), arr.get(index)) <= 0) break;
swap(index, bigSon);
index = bigSon;
l = index * 2 + 1;
}
}
private void swap(int i, int j) {
//元素位置互换
T t1 = arr.get(i);
T t2 = arr.get(j);
arr.set(i, t2);
arr.set(j, t1);
//元素位置互换后，更新元素位置表
indexMap.put(t1, j);
indexMap.put(t2, i);
}
}
TopK中奖者问题
给定一个整形数组，int[] arr; 和一个布尔类型数组，boolean[] op
两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
arr= [3,3,1,2,1,2,5…
op= [T,T,T,T,F,T,F…
依次表示：3用户购买了一件商品，3用户购买了1件商品，1用户购买了1件商品，2用户购买了1件商品
1用户退货了1件商品，2用户购买了1件商品，5用户退货了1件商品
一对arr[i]和op就代表一个事件：
用户号位arr[i]，op[i] == T就代表这个用户购买了一件商品
op[i] == F就代表这个用户退货了一件商品
现在你作为电商平台负责人，你想在每一个事件到来的时候，
都给购买次数最多的前K名用户颁奖。
所以每个事件发生后，你都需要一个得奖名单（得奖区）
得奖系统的规则：
1、 如果某个用户购买商品数位0，但是有发生了退货事件，则任务该事件无效，得奖名单和之前事件时一直，比如例子中的5用户；
2、 某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1；
3、 每次都是最多K个用户得奖，K也是作为参数传入，如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果；
4、 得奖系统分为得奖区和候选区，任何用户只要购买数>0，一定在这两个区域中的一个；
5、 购买数最大的前K名用户进入得奖区，在最初时入股得奖区没有到达K个用户，那么新进来的用户直接进入得奖区；
6、 如果购买数不足以进入得奖区的用户，进入候选区；
7、 如果候选区购买最多的用户，已经足以进入得奖区，该用户就会替换得奖区中购买数最少的用户（大于才能替换），如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户，如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户；
8、 候选区和得奖区是两套时间，因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有从得奖区出来进入候选区的用户，得奖区时间删除，进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i），从候选区出来进入得奖区的用户，候选区时间删除，进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）；
9、 如果某个用户购买数==0，不管在哪个区域都离开，区域时间删除，离开是指彻底离开，哪个区域都不会找到该用户，如果下次该用户又发生购买行为，产生>)的购买数，会再次根据之前规则回到某个区域中，进入区域的时间重记；
请遍历arr数组和op数组，遍历每一步输出一个得奖名单
public List
topK(int[] arr, boolean[] op, int k)
思路： 就是建立两个手写的堆，支持修改元素值后，动态调整
一个是候选者堆，按照购买数降序排序，购买数相同则按时间升序排序
一个是得奖者堆，按照购买数升序排序，购买数相同则按时间升序排序
然后遍历每一个事件，模拟事件发生，更新购买数，调整两个堆
候选者和得奖者交换，就是两个堆的堆顶PK一下，候选者堆顶PK赢了，就和得奖者堆顶交换
然后每一步遍历，都收一个得奖者堆的所有元素的id
/**
* 给定一个整形数组，int[] arr; 和一个布尔类型数组，boolean[] op
* 两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
* arr = [3,3,1,2,1,2,5...
* op = [T,T,T,T,F,T,F...
* 依次表示：3用户购买了一件商品，3用户购买了1件商品，1用户购买了1件商品，2用户购买了1件商品
* 1用户退货了1件商品，2用户购买了1件商品，5用户退货了1件商品
* 一对arr[i]和op就代表一个事件：
* 用户号位arr[i]，op[i] == T就代表这个用户购买了一件商品
* op[i] == F就代表这个用户退货了一件商品
* 现在你作为电商平台负责人，你想在每一个事件到来的时候，
* 都给购买次数最多的前K名用户颁奖。
* 所以每个事件发生后，你都需要一个得奖名单（得奖区）
* 得奖系统的规则：
* 1、如果某个用户购买商品数位0，但是有发生了退货事件，则任务该事件无效，得奖名单和之前事件时一直，比如例子中的5用户
* 2、某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
* 3、每次都是最多K个用户得奖，K也是作为参数传入，如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果
* 4、得奖系统分为得奖区和候选区，任何用户只要购买数>0，一定在这两个区域中的一个
* 5、购买数最大的前K名用户进入得奖区，在最初时入股得奖区没有到达K个用户，那么新进来的用户直接进入得奖区
* 6、如果购买数不足以进入得奖区的用户，进入候选区
* 7、如果候选区购买最多的用户，已经足以进入得奖区，该用户就会替换得奖区中购买数最少的用户（大于才能替换），如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户，如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户
* 8、候选区和得奖区是两套时间，因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有从得奖区出来进入候选区的用户，得奖区时间删除，进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i），从候选区出来进入得奖区的用户，候选区时间删除，进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
* 9、如果某个用户购买数==0，不管在哪个区域都离开，区域时间删除，离开是指彻底离开，哪个区域都不会找到该用户，如果下次该用户又发生购买行为，产生>)的购买数，会再次根据之前规则回到某个区域中，进入区域的时间重记
* 请遍历arr数组和op数组，遍历每一步输出一个得奖名单
* public List<List<Integer>> topK(int[] arr, boolean[] op, int k)
* Created by huangjunyi on 2022/11/20.
*/
public class Heap06 {
private Map<Integer, Customer> customerMap; // id和用户的索引表
private Heap05<Customer> candidateHeap; // 候选者堆 大根堆 按购买数降序排，购买数相同按时间升序排
private Heap05<Customer> winnerHeap; // 得奖者堆 小跟堆 按购买数升序排，购买数相同按时间降序排
private int K; // 指定得奖的用户数
public List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
this.K = k;
customerMap = new HashMap<>();
candidateHeap = new Heap05<>(((o1, o2) -> o1.buy != o2.buy ? o2.buy - o1.buy : o1.time - o2.time));
winnerHeap = new Heap05<>(((o1, o2) -> o1.buy != o2.buy ? o1.buy - o2.buy : o1.time - o2.time));
// 遍历所有事件 => 执行 => 获取得奖者名单
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
int id = arr[i];
boolean buy = op[i];
int time = i;
operate(id, buy, time);
res.add(getWinners());
}
return res;
}
/**
* 获取当前得奖者名单（id列表）
* @return
*/
private List<Integer> getWinners() {
// 直接取得奖者堆中所有元素的id
List<Customer> customers = winnerHeap.getALL();
return customers.stream().map(customer -> customer.id).collect(Collectors.toList());
}
/**
* 事件处理
* @param id 用户id
* @param buy 是否购买，购买 true，退货 false
* @param time 事件发生时间
*/
private void operate(int id, boolean buy, int time) {
// 规则1 如果某个用户购买商品数位0，但是有发生了退货事件，则任务该事件无效
if (!buy && !customerMap.containsKey(id)) return;
// 不存在该用户，先初始化
if (!customerMap.containsKey(id)) customerMap.put(id, new Customer(id, 0, 0));
// 更新用户购买数
Customer customer = customerMap.get(id);
if (buy) customer.buy++; else customer.buy--;
// 如果用户购买数位0，删除
if (customer.buy == 0) customerMap.remove(id);
// 更新候选者堆和得奖者堆
if (!candidateHeap.contains(customer) && !winnerHeap.contains(customer)) {
// 候选者堆和得奖者堆都没有该用户，代表是新用户
if (winnerHeap.size() < K) {
// 得奖者堆没满，直接进
customer.time = time;
winnerHeap.push(customer);
} else {
// 得奖者堆满了，先进入候选者堆
customer.time = time;
candidateHeap.push(customer);
}
} else if (candidateHeap.contains(customer)) {
// 候选者堆包含该用户，如果购买数为0，删掉，否者堆调整
if (customer.buy == 0) {
candidateHeap.remove(customer);
} else {
candidateHeap.resign(customer);
}
} else {
// 得奖者堆包含该用户，如果购买数为0，删掉，否者堆调整
if (customer.buy == 0) {
winnerHeap.remove(customer);
} else {
winnerHeap.resign(customer);
}
}
move(time);
}
private void move(int time) {
// 候选者堆空，返回
if (candidateHeap.size() == 0) return;
// 候选者堆不空，但是得奖者堆没满，那是前面删掉了一个得奖者
if (winnerHeap.size() < K) {
Customer pop = candidateHeap.pop();
pop.time = time;
winnerHeap.push(pop);
}
// 候选者堆不空，得奖者堆满了，如果候选者堆顶PK过了得奖者堆顶，交换
else {
if (candidateHeap.peek().buy > winnerHeap.peek().buy) {
Customer oldCandidate = candidateHeap.pop();
Customer oldWinner = winnerHeap.pop();
oldCandidate.time = time;
oldWinner.time = time;
winnerHeap.push(oldCandidate);
candidateHeap.push(oldWinner);
}
}
}
private class Customer {
int id;
int buy;
int time;
public Customer(int id, int buy, int time) {
this.id = id;
this.buy = buy;
this.time = time;
}
}
}