http://www.reibang.com/p/94155f9616bf
引入
在數(shù)據(jù)結(jié)構(gòu)中夸浅，普通的隊(duì)列是先進(jìn)先出，但有時(shí)我們可能并不想有這么固定的規(guī)矩扔役，我們希望能有一個(gè)帶優(yōu)先級(jí)的隊(duì)列帆喇。考慮在現(xiàn)實(shí)生活中亿胸，一些服務(wù)排隊(duì)窗口會(huì)寫著“軍人依法優(yōu)先”坯钦；送進(jìn)醫(yī)院的患者，即便是按順序到達(dá)的侈玄，生病更加嚴(yán)重的往往優(yōu)先級(jí)也會(huì)更高婉刀；還有操作系統(tǒng)中的作業(yè)調(diào)度也和優(yōu)先級(jí)有關(guān)......
于是我們能不能改進(jìn)隊(duì)列？使得隊(duì)列是有一定優(yōu)先級(jí)的序仙，這樣能讓一些事物和任務(wù)的處理變的更加靈活突颊。當(dāng)然是可以的，最基本的我們可以基于線性結(jié)構(gòu)來實(shí)現(xiàn)潘悼，考慮基于線性結(jié)構(gòu)的時(shí)間復(fù)雜度：
1律秃、隊(duì)列是一種FIFO（First-In-First-Out）先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，對(duì)應(yīng)于生活中的排隊(duì)的場(chǎng)景治唤，排在前面的人總是先通過棒动，依次進(jìn)行。
2宾添、優(yōu)先隊(duì)列是特殊的隊(duì)列船惨，從“優(yōu)先”一詞，可看出有“插隊(duì)現(xiàn)象”辞槐。比如在火車站排隊(duì)進(jìn)站時(shí)掷漱，就會(huì)有些比較急的人來插隊(duì)，他們就在前面先通過驗(yàn)票榄檬。優(yōu)先隊(duì)列至少含有兩種操作的數(shù)據(jù)結(jié)構(gòu)：insert（插入）卜范，即將元素插入到優(yōu)先隊(duì)列中（入隊(duì)）；以及deleteMin（刪除最小者）鹿榜，它的作用是找出海雪、刪除優(yōu)先隊(duì)列中的最小的元素（出隊(duì)）。
結(jié)構(gòu)\操作 入隊(duì) 出隊(duì)
普通線性結(jié)構(gòu) O(1) O(n)
順序線性結(jié)構(gòu) O(n) O(1)
普通線性結(jié)構(gòu)實(shí)現(xiàn)的優(yōu)先隊(duì)列出隊(duì)時(shí)間復(fù)雜度是O(n)舱殿，因?yàn)槌鲫?duì)要拿出最優(yōu)先的元素奥裸，也就是相對(duì)最大的元素（注意：大小是相對(duì)的，我們可以指定比較規(guī)則）沪袭，從而要掃描一遍整個(gè)數(shù)組選出最大的取出才行湾宙。而對(duì)于順序線性結(jié)構(gòu)的入隊(duì)操作，入隊(duì)后可能破壞了原來的有序性，從而要調(diào)整當(dāng)前順序侠鳄。
可以看到使用線性結(jié)構(gòu)總有時(shí)間復(fù)雜度是O(n)的操作埠啃，還有沒有更好的實(shí)現(xiàn)方式呢，當(dāng)然是有的伟恶，這就要來聊一聊堆Heap碴开。
堆
堆嚴(yán)格意義上來說又叫二叉堆（Binary Heap），因?yàn)樗慕Y(jié)構(gòu)是一顆完全二叉樹博秫，堆一般分為最大堆和最小堆潦牛。
堆性質(zhì)：
結(jié)構(gòu)性：堆是一顆除底層外被完全填滿的二叉樹，底層的節(jié)點(diǎn)從左到右填入挡育，這樣的樹叫做完全二叉樹巴碗。即缺失結(jié)點(diǎn)的部分一定再樹的右下側(cè)。
堆序性：由于我們想很快找出最小元静盅，則最小元應(yīng)該在根上良价，任意節(jié)點(diǎn)都小于它的后裔寝殴，這就是小頂堆（Min-Heap）蒿叠；如果是查找最大元，則最大元應(yīng)該在根上蚣常，任意節(jié)點(diǎn)都要大于它的后裔市咽，這就是大頂堆(Max-heap)。
堆的分類
最大堆：父親節(jié)點(diǎn)的值大于孩子節(jié)點(diǎn)的值
最小堆：父親節(jié)點(diǎn)的值小于孩子節(jié)點(diǎn)的值
數(shù)組表示堆
由于是完全二叉樹抵蚊，節(jié)點(diǎn)的索引之間有著一定的關(guān)系施绎，故我們可以使用數(shù)組來存儲(chǔ)二叉堆，具體如下：
如果從索引為0開始存儲(chǔ)贞绳，則父親和孩子節(jié)點(diǎn)的索引關(guān)系如下：
堆的實(shí)現(xiàn)
上浮操作(shift up)
當(dāng)我們需要向一個(gè)最大堆添加一條新的數(shù)據(jù)時(shí)谷醉，此時(shí)我們的堆變成了這樣。
此時(shí)冈闭，由于新數(shù)據(jù)的加入已經(jīng)不符合最大堆的定義了俱尼。所以我們需要對(duì)新加入的數(shù)據(jù)進(jìn)行shift up操作，將它放到它應(yīng)該在的位置萎攒。shift up操作時(shí)我們將新加入的數(shù)據(jù)與它的父節(jié)點(diǎn)進(jìn)行比較遇八。如果比它的父節(jié)點(diǎn)大，則交換二者耍休。
并且不斷的重復(fù)這個(gè)操作刃永，將它與父節(jié)點(diǎn)比較，直到它不大于父節(jié)點(diǎn)羊精，或者它沒有父節(jié)點(diǎn)（到頂了）斯够。
此時(shí)我們就完成了 對(duì)新加入元素的shift up操作。
下沉操作(shift down)
當(dāng)我們從堆中(也就是優(yōu)先隊(duì)列中)取出一個(gè)元素時(shí)。我們是將堆頂?shù)脑貜棾觥?只能從堆頂取出)
此時(shí)這個(gè)堆沒有頂了读规，那么該怎么辦呢劫灶？我們只需要把這個(gè)堆最后一個(gè)元素放到堆頂就可以了。
此時(shí)這個(gè)堆已經(jīng)不符合最大堆的性質(zhì)掖桦。為了保持這個(gè)性質(zhì)本昏，我們需要將堆頂?shù)脑卣{(diào)整到它應(yīng)該在的位置。也就是對(duì)它進(jìn)行shift Down操作枪汪。在shift down時(shí)涌穆，因?yàn)樗凶笥液⒆觾蓚€(gè)節(jié)點(diǎn)，所以我們需要將左右兩個(gè)孩子節(jié)點(diǎn)進(jìn)行比較雀久，在得到較大的節(jié)點(diǎn)之后宿稀，再與它進(jìn)行比較，如果它的子節(jié)點(diǎn)大赖捌，則將二者交換祝沸。并且不斷的重復(fù)這樣的操作，直到它沒有葉子節(jié)點(diǎn)或者大于葉子節(jié)點(diǎn)停止越庇。
此時(shí)我們就完成了彈出一個(gè)元素之后的shift down操作罩锐。
堆排序
replace
replace:去除最大元素后，放入一個(gè)新元素
實(shí)現(xiàn)：可以先extractMax,再add卤唉，兩次longn操作涩惑。
實(shí)現(xiàn):將堆頂?shù)脑靥鎿Q以后sift down，一次O(logn)操作
heapify
將n個(gè)元素逐個(gè)插入到一個(gè)空堆中,算法復(fù)雜度是O(nlogn),heapify的過程桑驱，算法的復(fù)雜度為O(n).
heapify:將任意數(shù)組整理成堆的形狀竭恬。
首先將一個(gè)數(shù)組抽象成一個(gè)堆。這個(gè)過程熬的，我們稱之為heapify痊硕。
之后我們找到這個(gè)堆中第一個(gè)非葉子節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的位置始終是數(shù)組的數(shù)量除以2押框，也就是索引5位置的27岔绸，從這個(gè)節(jié)點(diǎn)開始，對(duì)每一個(gè)非葉子的節(jié)點(diǎn),强戴，進(jìn)行shift down操作亭螟。
27比它的子節(jié)點(diǎn)51要小，所以交換二者骑歹。
之后對(duì)索引4位置的11预烙，以及索引3位置的25，繼續(xù)進(jìn)行shift down道媚。
接下來我們看索引2位置的20扁掸。首先呢翘县，我們需要將20與它兩個(gè)子節(jié)點(diǎn)中較大的51交換。
此時(shí)谴分，還沒有完锈麸，shift down操作是直到它沒有葉子節(jié)點(diǎn)或者大于葉子節(jié)點(diǎn)時(shí)才停止。
所以我們需要繼續(xù)將20與它的子節(jié)點(diǎn)27進(jìn)行比較牺蹄。
索引2才算操作完成了忘伞。
最后繼續(xù)對(duì)索引1位置的14，以此類推進(jìn)行shiftdown沙兰。整個(gè)堆就操作完成氓奈。使用的時(shí)候每次取出堆頂?shù)脑兀麄€(gè)數(shù)組就是排序完成的了鼎天。
heapfiy 的復(fù)雜度
每個(gè)節(jié)點(diǎn)堆化的時(shí)間復(fù)雜度是O(logn)舀奶，那個(gè)節(jié)點(diǎn)的堆化的總時(shí)間復(fù)雜度是O(nlogn)。
推導(dǎo)過程
堆化節(jié)點(diǎn)從倒數(shù)第二層開始斋射。堆化過程中育勺，需要比較和交換的節(jié)點(diǎn)個(gè)數(shù)與這個(gè)節(jié)點(diǎn)的高度k成正比。
將每個(gè)非葉子節(jié)點(diǎn)的高度求和罗岖，得到下面的公式S1:
這個(gè)公式的求解稍微有點(diǎn)技巧涧至，我們把公式左右都乘以2，得到另一個(gè)公式S2呀闻，再將S2減去S1化借，就可以得到S了潜慎。
S的中間部分是一個(gè)等比數(shù)列捡多，用等比數(shù)列的求和公式來計(jì)算，最終的結(jié)果就是下圖的樣子铐炫。
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=h%3D%5Clog_2%20n" alt="h=\log_2 n" mathimg="1">垒手，代入公式S，就得到S=O(n)倒信，所以建堆的時(shí)間復(fù)雜度是O(n)科贬。
原地堆排序
所以 heapify() 時(shí)間復(fù)雜度是 O(n).
建堆后，數(shù)組中的數(shù)據(jù)是大頂堆鳖悠。把堆頂元素榜掌，即最大元素，跟最后一個(gè)元素交換乘综，那最大元素就放到了下標(biāo)為n的位置憎账。
這個(gè)過程有點(diǎn)類似上面的“刪除堆頂元素”的操作，當(dāng)堆頂元素移除之后卡辰，把下標(biāo)n的元素放堆頂胞皱，然后再通過堆化的方法邪意，將剩下的n-1個(gè)元素重新構(gòu)建成堆。一直重復(fù)這個(gè)過程反砌，直到最后堆中只剩下下標(biāo)為1的元素雾鬼，排序就完成了。
// n表示數(shù)據(jù)的個(gè)數(shù)宴树，數(shù)組a中的數(shù)據(jù)從下標(biāo)1到n的位置策菜。
public class HeapSort {
public HeapSort() {
}
public static <E extends Comparable<E>> void sort(E[] data) {
MaxHeap<E> maxHeap = new MaxHeap();
for (E datum : data) {
maxHeap.add(datum);
}
for (int i = data.length - 1; i >= 0; i--) {
data[i] = maxHeap.extractMax();
}
}
//原地堆排序
public static <E extends Comparable<E>> void sort2(E[] data) {
if (data.length == 1) return;
//將數(shù)組整理成堆
//(data.length-2)/2:最后一個(gè)非葉子結(jié)點(diǎn)
//轉(zhuǎn)換成堆
for (int i = (data.length - 2) / 2; i >= 0; i--) {
siftDown(data, i, data.length);
}
//進(jìn)行堆排序
for (int i = data.length - 1; i >= 0; i--) {
swap(data, 0, i);
siftDown(data, 0, i);
}
}
//下沉操作
//對(duì)data[0,n)所形成的最大堆中，索引k的元素酒贬，執(zhí)行siftdown
private static <E extends Comparable<E>> void siftDown(E[] data, int k, int n) {
//結(jié)點(diǎn)k的左孩子已經(jīng)越界了,循環(huán)結(jié)束
while (2 * k + 1 < n) {
//左孩子的結(jié)點(diǎn)
int j = 2 * k + 1;
//右孩子的結(jié)點(diǎn),判斷有孩子是否存在做入，并且有孩子的值是否大于左孩子。
if (j + 1 < n && data[j + 1].compareTo(data[j]) > 0) {
j++;
}
//當(dāng)前值比孩子的值小
if (data[k].compareTo(data[j]) > 0) {
break;
}
//交換
swap(data, k, j);
k = j;
}
}
private static <E extends Comparable<E>> void swap(E[] data, int i, int j) {
E ele = data[i];
data[i] = data[j];
data[j] = ele;
}
public static void main(String[] args) {
Integer[] arr = {1, 65, 98, 65, 5, 65, 12};
sort2(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
代碼
package com.libin.setandmap;
import java.util.Random;
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap() {
this.data = new Array<>();
}
public int size() {
return data.getSize();
}
//返回一個(gè)布爾值同衣，表示堆中是否為空
public boolean isEmpty() {
return data.isEmpty();
}
//返回完全二叉樹數(shù)組表示中,一個(gè)索引表示的元素的父親結(jié)點(diǎn)的索引竟块。
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("index-0 doesn't dont have parent");
}
return (index - 1) / 2;
}
//返回完全二叉樹數(shù)組表示中,一個(gè)索引表示的元素的左孩子結(jié)點(diǎn)的索引。
private int leftChild(int index) {
return index * 2 + 1;
}
//返回完全二叉樹數(shù)組表示中,一個(gè)索引表示的元素的右孩子結(jié)點(diǎn)的索引耐齐。
private int rightChild(int index) {
return index * 2 + 2;
}
public void add(E e) {
data.addLast(e);
//上浮的元素
siftUp(data.getSize() - 1);
}
private void siftUp(int k) {
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
//與父節(jié)點(diǎn)進(jìn)行交換
data.swap(k, parent(k));
k = parent(k);
}
}
public E findMax() {
if (data.getSize() == 0) {
throw new IllegalArgumentException("empty");
}
return data.get(0);
}
public E extractMax() {
E max = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return max;
}
//下沉操作
private void siftDown(int k) {
//結(jié)點(diǎn)k的左孩子已經(jīng)越界了,循環(huán)結(jié)束
while (leftChild(k) < data.getSize()) {
//左孩子的結(jié)點(diǎn)
int j = leftChild(k);
//右孩子的結(jié)點(diǎn),判斷有孩子是否存在浪秘，并且有孩子的值是否大于左孩子。
if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j++;
}
//當(dāng)前值比孩子的值小
if (data.get(k).compareTo(data.get(j)) > 0) {
break;
}
//交換
data.swap(k, j);
k = j;
}
}
//去除最大元素,然后添加一個(gè)元素埠况。
public E replace(E e) {
E ret = findMax();
data.set(0, e);
siftDown(0);
return ret;
}
//heapfiy
public MaxHeap(E[] arr) {
data = new Array<>(arr);
//去除最后一個(gè)元素的父元素耸携。
for (int i = parent(arr.length - 1); i >= 0; i--) {
siftDown(i);
}
}
public static void main(String[] args) {
int n = 100;
Integer[] arr = new Integer[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
arr[i] =random.nextInt(Integer.MAX_VALUE);
}
MaxHeap<Integer> maxHeap = new MaxHeap<>(arr);
for (int i = 0; i < n; i++) {
System.out.println(maxHeap.extractMax());
}
System.out.println("finisehd");
}
}
package com.libin.setandmap;
import java.util.Arrays;
public class Array<E> {
private E[] data;
private int size;
//構(gòu)造函數(shù)，傳入數(shù)組的容量capacity的Array
@SuppressWarnings("unchecked")
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
//午參構(gòu)造函數(shù)辕翰，默認(rèn)capacity為10
public Array(){
this(10);
}
public Array(E[] arr){
data = (E[]) new Object[arr.length];
for (int i = 0; i <arr.length ; i++) {
data[i] = arr[i];
}
size = arr.length;
}
//獲取數(shù)組中元素個(gè)數(shù)
public int getSize(){
return size;
}
//獲取數(shù)組的容量
public int getCapacity(){
return data.length;
}
//判斷數(shù)組是否為空
public boolean isEmpty(){
return size == 0;
}
//在數(shù)組下標(biāo)為index的位置插入一個(gè)元素
public void add(int index , E e){
if(index<0||index>size){
throw new IllegalArgumentException("add failed , required index > 0 and index < size");
}
if(size == data.length){
resize(data.length * 2);
}
for(int i=size-1;i>index;i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
//向所有元素后添加一個(gè)新元素
public void addLast(E e){
add(size , e);
}
//向所有元素前添加一個(gè)新元素
public void addFirst(E e){
add(0 , e);
}
//獲取index索引位置的元素
public E get(int index){
if(index<0||index>=size){
throw new IllegalArgumentException("get failed , required index > 0 and index < size");
}
return data[index];
}
//修改索引index位置的元素為e
public void set(int index, E e){
if(index<0||index>=size){
throw new IllegalArgumentException("set failed , required index > 0 and index < size");
}
data[index] = e;
}
//判斷數(shù)組中是否含有元素e
public boolean contains(E e){
for(int i = 0;i<size;i++){
if(e.equals(data[i])){
return true;
}
}
return false;
}
//查找數(shù)組中是否含有元素e夺衍，返回相應(yīng)元素的下標(biāo)
public int find(E e){
for(int i = 0;i<size;i++){
if(e.equals(data[i])){
return i;
}
}
return -1;
}
//從數(shù)組中刪掉相應(yīng)下標(biāo)的元素，返回刪掉的元素
public E remove(int index){
if(index<0||index>=size){
throw new IllegalArgumentException("remove failed , required index > 0 and index < size");
}
E ret = data[index];
for(int i=index+1;i<size;i++){
data[i-1] = data[i];
}
size--;
data[size] = null;
if(size == data.length/4 && data.length/2 != 0){
resize(data.length/2);
}
return ret;
}
//從數(shù)組中刪掉第一個(gè)元素喜命，返回刪掉的元素
public E removeFirst(){
return remove(0);
}
//從數(shù)組中刪掉最后一個(gè)元素沟沙，返回刪掉的元素
public E removeLast(){
return remove(size-1);
}
//從數(shù)組中刪掉元素e
public void removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
}
}
public void swap(int i,int j){
E t = data[i];
data[i] = data[j];
data[j] =t;
}
@Override
public String toString() {
return "Array [data=" + Arrays.toString(data) + ", size=" + size +" Capacity="+data.length+ "]";
}
//重新設(shè)置數(shù)組容量
private void resize(int newCapacity){
@SuppressWarnings("unchecked")
E[] newData = (E[]) new Object[newCapacity];
for(int i=0;i<size; i++){
newData[i] = data[i];
}
data = newData;
}
}
優(yōu)先隊(duì)列
package com.libin.setandmap.heap;
public class PriorityQueue<E extends Comparable<E>>{
private MaxHeap<E> maxHeap;
public PriorityQueue() {
this.maxHeap = new MaxHeap();
}
public int getSize(){
return maxHeap.size();
}
public boolean isEmpty(){
return maxHeap.isEmpty();
}
public E getFront(){
return maxHeap.findMax();
}
public void enqueue(E e){
maxHeap.add(e);
}
public E deQueue(){
return maxHeap.extractMax();
}
}
快排思想和優(yōu)先隊(duì)列比較
topk和selectk問題既可以使用快排思想解決，也可以使用優(yōu)先隊(duì)列解決壁榕。
快排:O(n) 空間O(1)
優(yōu)先隊(duì)列:O(nlogk) 空間O(k)
優(yōu)先隊(duì)列的有i是矛紫，不需要一次性知道所有數(shù)據(jù),數(shù)據(jù)流的方式處理。
