二叉堆
一绍妨、實(shí)現(xiàn)的堆有如下特點(diǎn)
- 理論分析上為二叉堆
- 理論分析上為完全二叉樹
- 自定義堆的優(yōu)先級(jí)润脸，創(chuàng)建堆對(duì)象時(shí)需要實(shí)現(xiàn)比較器
- 底層用線性數(shù)組存取元素。
- 支持heapify操作他去，將一個(gè)數(shù)組進(jìn)行原地排序
二毙驯、如果索引從0開始開始編號(hào)，父子索引的關(guān)系如下
parent(i) = (i - 1) / 2
left child(i) = i * 2 + 1
right child(i) = i * 2 + 2
三灾测、具體實(shí)現(xiàn)
import java.util.ArrayList;
import java.util.Comparator;
/**
* 實(shí)現(xiàn)一個(gè)自定義優(yōu)先級(jí)的堆爆价。
* 要求用戶傳輸一個(gè)Lambda表達(dá)式指定是最大堆還是最小堆，或者其他定義媳搪！
* 很靈活是不是@_@
*/
public class MyHeap<E> {
private ArrayList<E> array;
private Comparator<E> compare;
// 構(gòu)造函數(shù)
public MyHeap(Comparator<E> compare){
array = new ArrayList<>();
this.compare = compare;
}
// 返回堆的大小
public int size() {
return array.size();
}
// 判斷堆是否為空
public boolean isEmpty() {
return this.size() == 0;
}
// swap交換函數(shù)
private void swap(int i, int j) {
E temp = array.get(i);
array.set(i, array.get(j));
array.set(j, temp);
}
// 計(jì)算父節(jié)點(diǎn)索引:parent(i) = (i - 1) / 2
private int parent(int i) {
return (i - 1) / 2;
}
// 計(jì)算左孩子節(jié)點(diǎn):left child(i) = i * 2 + 1
private int leftChild(int i) {
return i * 2 + 1;
}
// 計(jì)算右孩子節(jié)點(diǎn):right child(i) = i * 2 + 2
private int rightChild(int i) {
return i * 2 + 2;
}
// Shift Up操作铭段，將末尾元素與父元素比較,按照規(guī)則進(jìn)行交換！
private void shiftUp(int i) {
int parentIndex = parent(i);
while (i > 0 && compare.compare(array.get(i), array.get(parentIndex)) >= 0) {
swap(i, parentIndex);
i = parentIndex;
parentIndex = parent(parentIndex);
}
}
// 向堆中添加一個(gè)元素
public void add(E e) {
array.add(e);
shiftUp(array.size() - 1);
}
// 找到子節(jié)點(diǎn)優(yōu)先級(jí)最高的節(jié)點(diǎn)的索引
// 為了實(shí)現(xiàn)原地排序法秦爆，需要邊界參數(shù) boundary
// 如果沒有子節(jié)點(diǎn)則返回 -1
private int prioritySonIndex(int i, int boundary) {
int leftIndex = leftChild(i);
int rightIndex = rightChild(i);
if(leftIndex >= boundary)
return -1;
if(rightIndex >= boundary)
return leftIndex;
if(compare.compare(array.get(leftIndex), array.get(rightIndex)) > 0)
return leftIndex;
else
return rightIndex;
}
// Shift Down操作序愚，從根節(jié)點(diǎn)開始與子節(jié)點(diǎn)比較，按照規(guī)則進(jìn)行交換等限！
// 為了實(shí)現(xiàn)原地排序法爸吮，需要邊界參數(shù) boundary
private void shiftDown(int i, int boundary) {
int parent = i;
int son = prioritySonIndex(i, boundary);
while (son != -1) {
if(compare.compare(array.get(son), array.get(parent)) > 0) {
swap(parent, son);
parent = son;
son = prioritySonIndex(parent, boundary);
} else
return;
}
}
// 取出堆中的第一個(gè)元素芬膝，將最后一個(gè)元素
// 賦值到第一個(gè)元素的位置，然后進(jìn)行shift down操作形娇。
public E pop() {
try {
E temp = array.get(0);
array.set(0, array.get(array.size() - 1));
array.remove(array.size() - 1);
shiftDown(0, array.size());
return temp;
} catch (Exception e) {
throw new IndexOutOfBoundsException("數(shù)組索引越界錯(cuò)誤锰霜！");
}
}
/** @Heapify排序，將一個(gè)數(shù)組進(jìn)行排序
* 從最后一個(gè)含有子節(jié)點(diǎn)的節(jié)點(diǎn)開始一直到根節(jié)點(diǎn)桐早，進(jìn)行shift down操作
* 由于排序完畢之后是一個(gè)堆癣缅，需要進(jìn)行原地排序法將數(shù)組整理一下
* 思路：【排序后是倒敘，所以在創(chuàng)建 堆 時(shí)勘畔，得設(shè)計(jì)好優(yōu)先級(jí)所灸！】
* 1. Heapify完成之后，將第一個(gè)元素與最后一個(gè)元素交換炫七，進(jìn)行shift down操作【最后一個(gè)數(shù)不參與】
* 2. 將第一個(gè)元素與倒數(shù)第二個(gè)交換爬立，shift down操作【倒數(shù)第二個(gè)數(shù)之后的不參與】
* ...
* n. 直到第一個(gè)元素與交換的索引相等了，就終止
*/
public void heapify(ArrayList<E> arr){
this.array = arr;
int last = parent(arr.size() - 1);
for (int i = last; i >= 0; i--) {
shiftDown(i, array.size());
}
// 實(shí)現(xiàn)原地排序法
for (int i = array.size() - 1; i > 0; i --) {
swap(0, i);
shiftDown(0, i);
}
}
@Override
public String toString() {
return array.toString();
}
}
和堆相關(guān)的其他問題【以后探討】
在N個(gè)元素中選出前M個(gè)元素O(NlogM)【已實(shí)現(xiàn)】
-
多路歸并排序
多路并規(guī)排序.png d 叉堆 d-ary heap:每個(gè)節(jié)點(diǎn)有n個(gè)節(jié)點(diǎn)
最大堆万哪，最大索引堆侠驯，最小堆，最小索引堆【已滿足】
容量伸縮堆【已實(shí)現(xiàn)】
同時(shí)維護(hù)最大索引和最小索引
二項(xiàng)堆奕巍、斐波那契堆
