思考?
? 設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，用來(lái)存放整數(shù)，要求提供 3 個(gè)接口
- 添加元素
- 獲取最大值
- 刪除最大值
? 有沒(méi)有更優(yōu)的數(shù)據(jù)結(jié)構(gòu)？
堆
? 獲取最大值：O(1)、刪除最大值：O(logn)、添加元素：O(logn)
Top K問(wèn)題
? 什么是 Top K 問(wèn)題
從海量數(shù)據(jù)中找出前 K 個(gè)數(shù)據(jù)
? 比如
從 100 萬(wàn)個(gè)整數(shù)中找出最大的 100 個(gè)整數(shù)
? Top K 問(wèn)題的解法之一：可以用數(shù)據(jù)結(jié)構(gòu)“堆”來(lái)解決
堆（Heap）
? 堆（Heap）也是一種樹(shù)狀的數(shù)據(jù)結(jié)構(gòu)（不要跟內(nèi)存模型中的“堆空間”混淆），常見(jiàn)的堆實(shí)現(xiàn)有
- 二叉堆（Binary Heap，完全二叉堆）
- 多叉堆（D-heap、D-ary Heap）
- 索引堆（Index Heap）
- 二項(xiàng)堆（Binomial He p）
- 斐波那契堆（Fibonacci Heap）
- 左傾堆（Leftist Heap，左式堆）
- 斜堆（Skew Heap）
? 堆的一個(gè)重要性質(zhì)：任意節(jié)點(diǎn)的值總是 ≥（ ≤ ）子節(jié)點(diǎn)的值
如果任意節(jié)點(diǎn)的值總是 ≥ 子節(jié)點(diǎn)的值，稱為：最大堆、大根堆、大頂堆
如果任意節(jié)點(diǎn)的值總是 ≤ 子節(jié)點(diǎn)的值，稱為：最小堆、小根堆、小頂堆
? 由此可見(jiàn)，堆中的元素必須具備可比較性（跟二叉搜索樹(shù)一樣）
堆的基本接口設(shè)計(jì)
package com.njf;
public interface Heap <E>{
int size(); // 元素的數(shù)量
boolean isEmpty(); // 是否為空
void clear(); // 清空
void add(E element); // 添加元素
E get(); // 獲得堆頂元素
E remove(); // 刪除堆頂元素
E replace(E element); // 刪除堆頂元素的同時(shí)插入一個(gè)新元素
}
二叉堆（Binar y Heap）
? 二叉堆的邏輯結(jié)構(gòu)就是一棵完全二叉樹(shù)，所以也叫完全二叉堆
? 鑒于完全二叉樹(shù)的一些特性，二叉堆的底層（物理結(jié)構(gòu)）一般用數(shù)組實(shí)現(xiàn)即可
? 索引 i 的規(guī)律（ n 是元素?cái)?shù)量）
如果
i = 0 ，它是根節(jié)點(diǎn)如果
i > 0 ，它的父節(jié)點(diǎn)的索引為 floor( (i – 1) / 2 )如果
2i + 1 ≤ n – 1，它的左子節(jié)點(diǎn)的索引為 2i + 1如果
2i + 1 > n – 1 ，它無(wú)左子節(jié)點(diǎn)
如果 2i + 2 ≤ n – 1 ，它的右子節(jié)點(diǎn)的索引為 2i + 2
如果 2i + 2 > n – 1 ，它無(wú)右子節(jié)點(diǎn)
最大堆 – 添加
總結(jié)
? 循環(huán)執(zhí)行以下操作（圖中的 80 簡(jiǎn)稱為 node）
如果 node ＞ 父節(jié)點(diǎn)
? 與父節(jié)點(diǎn)交換位置
如果 node ≤ 父節(jié)點(diǎn)，或者 node 沒(méi)有父節(jié)點(diǎn)
? 退出循環(huán)
? 這個(gè)過(guò)程，叫做上濾（Sift Up）
時(shí)間復(fù)雜度：O(logn)
@Override
public void add(E element) {
//二叉堆節(jié)點(diǎn)元素具備可比較性，所以添加元素不能為空
elementNotNullCheck(element);
//擴(kuò)容
ensureCapacity(size + 1);
//在數(shù)組的尾部添加元素
elements[size] = element;
//上濾
siftUp(size);
size ++;
}
/**
* 讓index位置的元素上濾
* @param index
*/
private void siftUp(int index) {
E element = elements[index];
while (index > 0) {//只有index > 0 才會(huì)觸發(fā)上濾
//獲取父節(jié)點(diǎn)的index
int parentIndex = (index - 1) >> 1;
E parentElement = elements[parentIndex];
if (compare(element, parentElement) <= 0) return;
// 交換index、parentIdex位置的內(nèi)容
E tmp = elements[index];
elements[index] = elements[parentIndex];
elements[parentIndex] = tmp;
//重新賦值index，開(kāi)啟下一輪循環(huán)
index = parentIndex;
}
}
最大堆 – 添加 – 交換位置的優(yōu)化
? 一般交換位置需要3行代碼，可以進(jìn)一步優(yōu)化
將新添加節(jié)點(diǎn)備份，確定最終位置才擺放上去
? 僅從交換位置的代碼角度看
可以由大概的 3 * O(logn) 優(yōu)化到 1 * O(logn) + 1
/**
* 讓index位置的元素上濾
* @param index
*/
private void siftUp(int index) {
E element = elements[index];
while (index > 0) {//只有index > 0 才會(huì)觸發(fā)上濾
//獲取父節(jié)點(diǎn)的index
int parentIndex = (index - 1) >> 1;
E parentElement = elements[parentIndex];
if (compare(element, parentElement) <= 0) break;
// 交換index、parentIdex位置的內(nèi)容
elements[index] = elements[parentIndex];
//重新賦值index，開(kāi)啟下一輪循環(huán)
index = parentIndex;
}
elements[index] = element;
}
最大堆 – 刪除
總結(jié)
1. 用最后一個(gè)節(jié)點(diǎn)覆蓋根節(jié)點(diǎn)
2. 刪除最后一個(gè)節(jié)點(diǎn)
3. 循環(huán)執(zhí)行以下操作（圖中的 43 簡(jiǎn)稱為 node）
如果 node < 最大的子節(jié)點(diǎn)
? 與最大的子節(jié)點(diǎn)交換位置
如果 nod ≥ 最大的子節(jié)點(diǎn)， 或者 node 沒(méi)有子節(jié)點(diǎn)
? 退出循環(huán)
? 這個(gè)過(guò)程，叫做下濾（Sift Down），時(shí)間復(fù)雜度：O(logn)
? 同樣的，交換位置的操作可以像添加那樣進(jìn)行優(yōu)化
@Override
public E remove() {
emptyCheck();
E root = elements[0];
elements[0] = elements[size -1];
elements[size - 1] = null;
size --;
siftDown(0);
return root;
}
下濾
/**
* 讓index位置的元素下濾
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// 第一個(gè)葉子節(jié)點(diǎn)的索引 == 非葉子節(jié)點(diǎn)的數(shù)量
// index < 第一個(gè)葉子節(jié)點(diǎn)的索引
// 必須保證index位置是非葉子節(jié)點(diǎn)
while (index < half) {
// index的節(jié)點(diǎn)有2種情況
// 1.只有左子節(jié)點(diǎn)
// 2.同時(shí)有左右子節(jié)點(diǎn)
// 默認(rèn)為左子節(jié)點(diǎn)跟它進(jìn)行比較
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 右子節(jié)點(diǎn)
int rightIndex = childIndex + 1;
// 選出左右子節(jié)點(diǎn)最大的那個(gè)
if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
child = elements[childIndex = rightIndex];
}
if (compare(element, child) >= 0) break;
// 將子節(jié)點(diǎn)存放到index位置
elements[index] = child;
// 重新設(shè)置index
index = childIndex;
}
elements[index] = element;
}
完全二叉樹(shù)的性質(zhì)：非葉子結(jié)點(diǎn)個(gè)數(shù) n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )
break 跳出總上一層循環(huán)，不再執(zhí)行循環(huán)(結(jié)束當(dāng)前的循環(huán)體)
continue 跳出本次循環(huán)，繼續(xù)執(zhí)行下次循環(huán)(結(jié)束正在執(zhí)行的循環(huán) 進(jìn)入下一個(gè)循環(huán)條件)
return 程序返回，不再執(zhí)行下面的代碼(結(jié)束當(dāng)前的方法 直接返回)
最大堆 – 批量建堆（Heapify）
? 批量建堆，有 2 種做法
- 自上而下的上濾
- 自下而上的下濾
最大堆 – 批量建堆 – 自上而下的上濾
for (int i = 1; i < size; i++) {
siftUp(i);
}
最大堆 – 批量建堆 – 自下而上的下濾
// 自下而上的下濾
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
最大堆 – 批量建堆 – 效率對(duì)比
? 所有節(jié)點(diǎn)的深度之和
僅僅是葉子節(jié)點(diǎn)，就有近 n/2 個(gè)，而且每一個(gè)葉子節(jié)點(diǎn)的深度都是 O(logn) 級(jí)別的
因此，在葉子節(jié)點(diǎn)這一塊，就達(dá)到了 O(nlogn) 級(jí)別
O(nlogn) 的時(shí)間復(fù)雜度足以利用排序算法對(duì)所有節(jié)點(diǎn)進(jìn)行全排序
? 所有節(jié)點(diǎn)的高度之和
假設(shè)是滿樹(shù)，節(jié)點(diǎn)總個(gè)數(shù)為 n，樹(shù)高為 h，那么 n = 2^h ? 1
公式推導(dǎo)
public BinaryHeap(E[] elements,Comparator<E> comparator) {
this.comparator = comparator;
if (elements == null || elements.length == 0) {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}else {
size = elements.length;
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
//批量建堆
heapify();
}
}
/**
* 批量建堆
*/
private void heapify() {
// 自上而下的上濾
// for (int i = 1; i < size; i++) {
// siftUp(i);
// }
// 自下而上的下濾
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}
如何構(gòu)建一個(gè)小頂堆？
Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
Top K問(wèn)題
? 從 n 個(gè)整數(shù)中，找出最大的前 k 個(gè)數(shù)（ k 遠(yuǎn)遠(yuǎn)小于 n ）
? 如果使用排序算法進(jìn)行全排序，需要 O(nlogn) 的時(shí)間復(fù)雜度
? 如果使用二叉堆來(lái)解決，可以使用 O(nlogk) 的時(shí)間復(fù)雜度來(lái)解決
1. 新建一個(gè)小頂堆
2. 掃描 n 個(gè)整數(shù)
? 先將遍歷到的前 k 個(gè)數(shù)放入堆中
? 從第 k + 1 個(gè)數(shù)開(kāi)始，如果大于堆頂元素，就使用 replace 操作（刪除堆頂元素，將第 k + 1 個(gè)數(shù)添加到堆中）
3. 掃描完畢后，堆中剩下的就是最大的前 k 個(gè)數(shù)
// 新建一個(gè)小頂堆
BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
// 找出最大的前k個(gè)數(shù)
int k = 3;
Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
90, 6, 65, 49, 3, 26, 61, 21, 48};
for (int i = 0; i < data.length; i++) {
if (heap.size() < k) { // 前k個(gè)數(shù)添加到小頂堆
heap.add(data[i]); // logk
} else if (data[i] > heap.get()) { // 如果是第k + 1個(gè)數(shù)，并且大于堆頂元素
heap.replace(data[i]); // logk
}
}
? 如果是找出最小的前 k 個(gè)數(shù)呢？
用大頂堆
如果小于堆頂元素，就使用 replace 操作
二叉堆的完整代碼
package com.njf;
import java.util.Comparator;
import njf.printer.BinaryTreeInfo;
@SuppressWarnings("unused")
public class BinaryHeap<E> implements Heap<E>,BinaryTreeInfo{
private static final int DEFAULT_CAPACITY = 10;
private int size;
private E[] elements;
private Comparator<E> comparator;
public BinaryHeap(E[] elements,Comparator<E> comparator) {
this.comparator = comparator;
if (elements == null || elements.length == 0) {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}else {
size = elements.length;
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
//批量建堆
heapify();
}
}
public BinaryHeap (E[] elements) {
this(elements,null);
}
public BinaryHeap (Comparator<E> comparator) {
this(null,comparator);
}
public BinaryHeap () {
this(null,null);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
@Override
public void add(E element) {
//二叉堆節(jié)點(diǎn)元素具備可比較性，所以添加元素不能為空
elementNotNullCheck(element);
//擴(kuò)容
ensureCapacity(size + 1);
//在數(shù)組的尾部添加元素
elements[size] = element;
//上濾
siftUp(size);
size ++;
}
@Override
public E get() {
//檢測(cè)二叉對(duì)是否為空
emptyCheck();
return elements[0];
}
@Override
public E remove() {
emptyCheck();
E root = elements[0];
elements[0] = elements[size -1];
elements[size - 1] = null;
size --;
siftDown(0);
return root;
}
@Override
public E replace(E element) {
elementNotNullCheck(element);
if (size == 0) {
elements[0] = element;
size ++;
}else {
E root = elements[0];
elements[0] = element;
siftDown(0);
return root;
}
return null;
}
/**
* 批量建堆
*/
private void heapify() {
// 自上而下的上濾
// for (int i = 1; i < size; i++) {
// siftUp(i);
// }
// 自下而上的下濾
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}
/**
* 讓index位置的元素下濾
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
//完全二叉樹(shù)的性質(zhì)：非葉子結(jié)點(diǎn)個(gè)數(shù) n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )
int half = size >> 1;
// 第一個(gè)葉子節(jié)點(diǎn)的索引 == 非葉子節(jié)點(diǎn)的數(shù)量
// index < 第一個(gè)葉子節(jié)點(diǎn)的索引
// 必須保證index位置是非葉子節(jié)點(diǎn)
while (index < half) {
// index的節(jié)點(diǎn)有2種情況
// 1.只有左子節(jié)點(diǎn)
// 2.同時(shí)有左右子節(jié)點(diǎn)
// 默認(rèn)為左子節(jié)點(diǎn)跟它進(jìn)行比較
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
// 右子節(jié)點(diǎn)
int rightIndex = childIndex + 1;
// 選出左右子節(jié)點(diǎn)最大的那個(gè)
if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
child = elements[childIndex = rightIndex];
}
if (compare(element, child) >= 0) break;
// 將子節(jié)點(diǎn)存放到index位置
elements[index] = child;
// 重新設(shè)置index
index = childIndex;
}
elements[index] = element;
}
/**
* 讓index位置的元素上濾
* @param index
*/
private void siftUp(int index) {
// E element = elements[index];
// while (index > 0) {//只有index > 0 才會(huì)觸發(fā)上濾
// //獲取父節(jié)點(diǎn)的index
// int parentIndex = (index - 1) >> 1;
// E parentElement = elements[parentIndex];
// if (compare(element, parentElement) <= 0) return;
// // 交換index、parentIdex位置的內(nèi)容
// E tmp = elements[index];
// elements[index] = elements[parentIndex];
// elements[parentIndex] = tmp;
// //重新賦值index，開(kāi)啟下一輪循環(huán)
// index = parentIndex;
// }
E element = elements[index];
while (index > 0) {//只有index > 0 才會(huì)觸發(fā)上濾
//獲取父節(jié)點(diǎn)的index
int parentIndex = (index - 1) >> 1;
E parentElement = elements[parentIndex];
if (compare(element, parentElement) <= 0) break;
// 交換index、parentIdex位置的內(nèi)容
elements[index] = elements[parentIndex];
//重新賦值index，開(kāi)啟下一輪循環(huán)
index = parentIndex;
}
elements[index] = element;
}
/**
* 保證要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);//位運(yùn)算
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}
private int compare(E e1, E e2) {
return comparator != null ? comparator.compare(e1, e2) : ((Comparable<E>)e1).compareTo(e2);
}
private void emptyCheck() {
if (size == 0) {
throw new IndexOutOfBoundsException("Heap is empty");
}
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
/********************二叉樹(shù)的打印****************/
@Override
public Object root() {
return 0;
}
@Override
public Object left(Object node) {
int index = ((int)node << 1) + 1;
return index >= size ? null : index;
}
@Override
public Object right(Object node) {
int index = ((int)node << 1) + 2;
return index >= size ? null : index;
}
@Override
public Object string(Object node) {
return elements[(int)node];
}
}
驗(yàn)證
package com.njf;
import java.util.Comparator;
import njf.printer.BinaryTrees;
public class Main {
private static void test() {
BinaryHeap <Integer> heap = new BinaryHeap<>();
heap.add(68);
heap.add(72);
heap.add(43);
heap.add(50);
heap.add(38);
heap.add(10);
heap.add(90);
heap.add(65);
BinaryTrees.println(heap);
// heap.remove();
// BinaryTrees.println(heap);
System.out.println(heap.replace(70));
BinaryTrees.println(heap);
}
static void test1() {
Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
BinaryHeap<Integer> heap = new BinaryHeap<>(data);
BinaryTrees.println(heap);
data[0] = 10;
data[1] = 20;
BinaryTrees.println(heap);
}
static void test2() {
Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
BinaryTrees.println(heap);
}
static void test3() {
// 新建一個(gè)小頂堆
BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
// 找出最大的前k個(gè)數(shù)
int k = 3;
Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
90, 6, 65, 49, 3, 26, 61, 21, 48};
for (int i = 0; i < data.length; i++) {
if (heap.size() < k) { // 前k個(gè)數(shù)添加到小頂堆
heap.add(data[i]); // logk
} else if (data[i] > heap.get()) { // 如果是第k + 1個(gè)數(shù)，并且大于堆頂元素
heap.replace(data[i]); // logk
}
}
// O(nlogk)
BinaryTrees.println(heap);
}
public static void main(String[] args) {
test3();
}
}
