可以利用堆撬讽、外排序的方法來(lái)做多個(gè)處理單元的結(jié)果合并
寫在前面：
堆通常是一個(gè)可以被看做一棵`完全二叉樹的數(shù)組對(duì)象`蕊连，
小根堆，最小值在`arr[0]`游昼； 大根堆咪奖，最大值在`arr[0]`
插入節(jié)點(diǎn)的時(shí)間復(fù)雜度是`O(log(n))`,獲取最值的時(shí)間復(fù)雜度是`O(1)`
堆，其實(shí)就是一個(gè)完全二叉樹酱床；
完全二叉樹，要么是一個(gè)滿二叉樹趟佃，要么葉子節(jié)點(diǎn)層為從左到右扇谣；
堆，實(shí)際中是可以用數(shù)組實(shí)現(xiàn)的闲昭；
規(guī)律罐寨，把數(shù)組腦補(bǔ)成完全二叉樹
節(jié)點(diǎn) n 的左孩子為 2*n + 1,也就是 n<<1 +1
節(jié)點(diǎn) n 的左孩子為 2*n + 2,也就是 n<<1 +2
節(jié)點(diǎn) n 的父節(jié)點(diǎn)為 (n-1)/2,也就是 (n-1)>>2
堆分為小根堆、大根堆
小根堆：在完全二叉樹中序矩，任何一個(gè)子樹的最小值都在頭部鸯绿，小根堆，數(shù)組最小值在arr[0]
大根堆：在完全二叉樹中簸淀，任何一個(gè)子樹的最大值都在頭部瓶蝴，大根堆，數(shù)組最大值在arr[0]
堆排序
思想：1租幕、根據(jù)大根堆的特點(diǎn)舷手，先將一個(gè)數(shù)組構(gòu)建成為一個(gè)大根堆，這樣堆頂就是最大的
2劲绪、再將堆頂和最后一個(gè)數(shù)互換男窟，將最大的數(shù)放到最后盆赤，隨即調(diào)整維持大根堆
繼續(xù)互換、調(diào)整歉眷。
public void heapSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 1牺六、將整個(gè)數(shù)組構(gòu)建成為大根堆數(shù)組
for (int i = 1; i < arr.length; i++) {
maxHeapInsert(arr, i);
}
// 2、將大根堆對(duì)頂(index為0)的數(shù)換到最后去汗捡，再heapify調(diào)整大根堆
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i - 1);
}
}
/**
* 在arr尾部新增一個(gè)數(shù)淑际，繼續(xù)保持arr是大根堆
* arr 在 p 之前已經(jīng)是一個(gè)大根堆了，現(xiàn)在加入的 p 的數(shù)凉唐，需要維持 [a,p]是一個(gè)大根堆
* 實(shí)現(xiàn)原理：聯(lián)想大根堆的特點(diǎn)庸追，插入的數(shù)如果比父節(jié)點(diǎn)大，則向上交換台囱，一直到小于父節(jié)點(diǎn)或者堆頂
* 下標(biāo)小于0 的情況考慮到的
*
* @param arr 傳入的數(shù)組
* @param p 指針淡溯，表示即將加入的節(jié)點(diǎn)
*/
private void maxHeapInsert(int[] arr, int p) {
while (arr[p] > arr[(p - 1) / 2]) {
swap(arr, p, (p - 1) / 2);
p = (p - 1) / 2;
}
}
/**
* 大根堆位于index的數(shù)與最后一個(gè)數(shù)互換之后，調(diào)整arr繼續(xù)保持大根堆
* 在本例堆排序中簿训，是一直將大根堆的最后一個(gè)和第一個(gè)互換咱娶，也就是將最大的值放到最后
*
* @param arr 傳入的數(shù)組
* @param index 被改變的數(shù)的下標(biāo)，將一直為0
* @param lastIndex 大根堆的最后一個(gè)index
*/
private void heapify(int[] arr, int index, int lastIndex) {
// index的左孩子
int left = index * 2 + 1;
while (left <= lastIndex) {
// 判斷是否有右孩子强品，如果有比較左右孩子的大小膘侮，選擇較大的一個(gè)的indx
int largerSonIndex = left + 1 <= lastIndex && arr[left + 1] > arr[left] ? left + 1 : left;
// 如果父節(jié)點(diǎn)比孩子節(jié)點(diǎn)都大的話，就不用調(diào)整了的榛，直接返回
if (arr[index] >= arr[largerSonIndex]) {
return;
}
// 父節(jié)點(diǎn)與較大的孩子交換
swap(arr, index, largerSonIndex);
index = largerSonIndex;
left = index * 2 + 1;
}
}
應(yīng)用：
1琼了、優(yōu)先級(jí)隊(duì)列
java實(shí)現(xiàn)的堆結(jié)構(gòu)、優(yōu)先級(jí)隊(duì)列夫晌，PriorityQueue()
PriorityQueue當(dāng)size達(dá)到了初始的initialCapacity容量后會(huì)進(jìn)行擴(kuò)容雕薪，每次容量加1。
| = | fun | 時(shí)間復(fù)雜度 |
|---|---|---|
| 插入到堆中 | add() | O(logn) |
| 取出晓淀、刪除堆頂 | poll() | O(logn) |
| get堆頂 | peek() | O(1) |
| 堆的大小 | size() |
// 默認(rèn)小頂堆所袁，默認(rèn)容量為11
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 添加比較器，實(shí)現(xiàn)大頂堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, (i1, i2) -> i2-i1);
//添加數(shù)據(jù)
int []arr={2,3,1,4,2,0,5,7};
for (int each : arr) {
minHeap.add(each);
maxHeap.add(each);
}
while(minHeap.size()>0){
System.out.print(minHeap.poll()+" ");
}
System.out.println("\n=====");
while(maxHeap.size()>0){
System.out.print(maxHeap.poll()+" ");
}
0 1 2 2 3 4 5 7
=====
7 5 4 3 2 2 1 0
2凶掰、統(tǒng)計(jì)流中的中位數(shù)：
| 數(shù)據(jù)結(jié)構(gòu) | 插入的時(shí)間復(fù)雜度 | 得到中位數(shù)的時(shí)間復(fù)雜度 | 細(xì)節(jié) |
|---|---|---|---|
| 沒(méi)有排序的數(shù)組 | O(1) | O(n) | 使用分治的方法 |
| 排序的數(shù)組 | O(n) | O(1) | ddd |
| 排序的鏈表 | O(n) | O(1) | 定義兩指針指向中間節(jié)點(diǎn) |
| 二叉搜索樹 | 平均O(logn) | 平均O(logn) | 最差O(n) |
| AVL樹 | O(logn) | O(1) | 中位數(shù)在root |
| 大根堆小根堆 | O(logn) | O(1) | 如下 |
1->1
1,2->1.5
1,2,3->2
...
準(zhǔn)備一個(gè)大根堆燥爷，一個(gè)小根堆
把小于等于大根堆對(duì)頂?shù)臉洳迦氪蟾眩?br>
把大于大根堆對(duì)頂?shù)臉洳迦胄「眩?br>
同時(shí)，要調(diào)整大根堆和小根堆的數(shù)量懦窘，數(shù)量差值不要超過(guò)1前翎；
如果大根堆的size大了，就把大根堆 的堆頂取出插入小根堆畅涂；
如果小根堆的size大了鱼填，就把小根堆 的堆頂取出插入大根堆；
這樣就能達(dá)到毅戈，大根堆苹丸，小根堆數(shù)量保持平衡愤惰，同時(shí)大根堆中的小的n/2個(gè)數(shù)，小根堆中是大的n/2個(gè)數(shù)赘理，
（大根堆堆頂+小根堆堆頂）/2 就是流的中位數(shù)
3宦言、合并有序小文件
假設(shè)我們有 100 個(gè)小文件，每個(gè)文件的大小是 100MB商模，每個(gè)文件中存儲(chǔ)的都是有序的字符串奠旺。我們希望將這些 100 個(gè)小文件合并成一個(gè)有序的大文件。
思路：利用一個(gè)小根堆施流，把每個(gè)文件的第一條記錄取出來(lái)响疚，放入小根堆中，那么小根堆的堆頂就是這100條記錄中順序最小的記瞪醋，它為記錄A忿晕，也是這100個(gè)文件中順序最小的，將這個(gè)堆頂追加到準(zhǔn)備的大文件银受。從記錄A原來(lái)所在的文件中再取出一條記錄践盼，放入小根堆，取出堆頂宾巍，如此重復(fù)...
4咕幻、高性能定時(shí)器
5、利用堆求 Top K
思路：利用一個(gè)size為k的堆顶霞，求最大的Top K 用小根堆 肄程，求最小的Top k用大根堆。
我們可以維護(hù)一個(gè)大小為 K 的小頂堆选浑，順序遍歷數(shù)組蓝厌，從數(shù)組中取出取數(shù)據(jù)與堆頂元素比較。如果比堆頂元素大鲜侥，我們就把堆頂元素刪除，并且將這個(gè)元素插入到堆中诸典；如果比堆頂元素小描函，則不做處理，繼續(xù)遍歷數(shù)組狐粱。這樣等數(shù)組中的數(shù)據(jù)都遍歷完之后舀寓，堆中的數(shù)據(jù)就是前 K 大數(shù)據(jù)了。
遍歷數(shù)組需要 O(n) 的時(shí)間復(fù)雜度肌蜻，一次堆化操作需要 O(logK) 的時(shí)間復(fù)雜度互墓，所以最壞情況下，n 個(gè)元素都入堆一次蒋搜，所以時(shí)間復(fù)雜度就是 O(nlogK)篡撵。
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if(input == null || input.length < k || k <=0 || input.length == 0){
return new ArrayList<>();
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,(x,y)->y-x);
for(int i = 0;i<k;i++){
maxHeap.add(input[i]);
}
for(int i = k ;i<input.length;i++){
if(input[i] < maxHeap.peek()){
maxHeap.poll();
maxHeap.add(input[i]);
}
}
return new ArrayList<>(maxHeap);
}
6判莉、假設(shè)現(xiàn)在我們有一個(gè)包含 10 億個(gè)搜索關(guān)鍵詞的日志文件，如何能快速獲取到熱門榜 Top 10 的搜索關(guān)鍵詞呢育谬，單機(jī)券盅，可以使用的內(nèi)存為 1GB？
使用map<key,count>計(jì)數(shù)膛檀，count放入小根堆中锰镀，多個(gè)小根堆合并求top10.
分析：假設(shè)一條搜索50個(gè)字節(jié)，10億條那么就占用了50GB的大小咖刃，所以一次對(duì)所有數(shù)據(jù)進(jìn)行統(tǒng)計(jì)是不可行的泳炉。
0、準(zhǔn)備10個(gè)空文件
1嚎杨、采用hash 算法將日志進(jìn)行計(jì)算之后得到hash值花鹅，模10，存放入對(duì)應(yīng)的文件中磕潮。那么每個(gè)文件大概會(huì)有1億條記錄翠胰，假設(shè)平均每條關(guān)鍵詞重復(fù)10次，那么就是1000萬(wàn)條關(guān)鍵詞自脯，大概500MB之景，1G的內(nèi)存是可以存下的
2、使用hashmap對(duì)每個(gè)小文件中的關(guān)鍵詞進(jìn)行數(shù)量統(tǒng)計(jì)膏潮，對(duì)每個(gè)小文件的統(tǒng)計(jì)的結(jié)果存入一個(gè)Size為10 的小根堆锻狗。
3、對(duì)這10個(gè)小根堆再進(jìn)行合并得到最終的Top 10 的搜索關(guān)鍵詞
