索引堆
對于一個算法扛点，如果僅僅是實現(xiàn)出來透葛，而不能很好的用語言進行表達，說明對于此算法的理解還比較模糊镀裤，如果能夠清晰的表述出來竞阐，那么對于此算法的理解就足夠清晰了！
原數組
array的位置不變暑劝，用一個新的數組indexArr存儲原數組的索引骆莹，在用一個數組reverseArr存儲array中元素對應的索引在indexArr數組中的位置，他們的關系如下担猛，利用這些特性可以讓索引堆的平均性能更優(yōu)幕垦。
索引的索引.png
import java.util.ArrayList;
import java.util.Comparator;
/** @索引堆
*/
public class IndexHeap<E> {
private ArrayList<E> array; // 原始數組
private ArrayList<Integer> indexArr; // 索引堆
private ArrayList<Integer> reverseArr; // 原始數組元素的索引在索引堆中的位置
private Comparator<E> compare;
// 構造函數
public IndexHeap(Comparator<E> compare){
array = new ArrayList<>();
indexArr = new ArrayList<>();
reverseArr = new ArrayList<>();
this.compare = compare;
}
public int size() {
return array.size();
}
public boolean isEmpty() {
return this.size() == 0;
}
/** @swap 交換函數,交換索引堆,同時維護一下索引堆指向的數據
* 索引堆 與 索引指向 之間的關系
* @索引堆 : indexArr[i] = j
* @索引指向: reverseArr[j] = i
* reverseArr[indexArr[i]] = i;
* indexArr[reverseArr[j]] = j;
*
* @注意： 維護索引指向丢氢，不能像下面這樣耍，可能會造成索引指向重復
* reverseArr.set(indexArr.get(i), i);
* reverseArr.set(indexArr.get(j), j);
*/
private void swap(int i, int j) {
// 維護索引堆
Integer temp = indexArr.get(i);
indexArr.set(i, indexArr.get(j));
indexArr.set(j, temp);
// 維護索引執(zhí)行
int revI = indexArr.get(i);
int revJ = indexArr.get(j);
int exchange = reverseArr.get(revI);
reverseArr.set(revI, reverseArr.get(revJ));
reverseArr.set(revJ, exchange);
}
/** 計算父節(jié)點索引:parent(i) = (i - 1) / 2*/
private int parent(int i) {
return (i - 1) / 2;
}
/** 計算左孩子節(jié)點:left child(i) = i * 2 + 1*/
private int leftChild(int i) {
return i * 2 + 1;
}
/** 計算右孩子節(jié)點:right child(i) = i * 2 + 2*/
private int rightChild(int i) {
return i * 2 + 2;
}
/** @shiftUp先改，
* 將優(yōu)先級大的往上冒
* 注意：實際比較的是索引堆值指向源數組中的數據
* swap交換是索引堆的值
*/
private void shiftUp(int i) {
int parentIndex = parent(i);
while (i > 0 && compare.compare(array.get(indexArr.get(i)), array.get(indexArr.get(parentIndex))) >= 0) {
swap(i, parentIndex);
i = parentIndex;
parentIndex = parent(parentIndex);
}
}
/** @向堆中添加一個元素
* 同步向索引堆和索引堆指向中添加數組
*/
public void add(E e) {
array.add(e);
indexArr.add(array.size() - 1);
reverseArr.add(indexArr.size() - 1);
// 對索引數組進行排序
shiftUp(indexArr.size() - 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(indexArr.get(leftIndex)), array.get(indexArr.get(rightIndex))) > 0)
return leftIndex;
else
return rightIndex;
}
// Shift Down操作疚察，從根節(jié)點開始與子節(jié)點比較，按照規(guī)則進行交換仇奶！
private void shiftDown(int i, int boundary) {
int parent = i;
int son = prioritySonIndex(i, boundary);
while (son != -1) {
if(compare.compare(array.get(indexArr.get(son)), array.get(indexArr.get(parent))) > 0) {
swap(parent, son);
parent = son;
son = prioritySonIndex(parent, boundary);
} else
return;
}
}
/** @pop 找到堆中的第一個元素所指向的原始數組的值貌嫡，也就是優(yōu)先級最大的元素。
* 1. 如果原始數組中刪除一個元素该溯，此元素的索引【i】之后的所有元素都會前移動一位
* 索引堆中對應的大于上面索引【i】的索引堆指向都向后多了一位的指向岛抄，需要將
* 他們的值減去1，向前偏移一位狈茉！
* 2. 移除原始數組array中的被返回的數組
* 3. 將索引指向堆reverseArr中對應【indexArr堆中末尾】的指向
* 賦值到對應【indexArr堆中首位】的位置夫椭；
* 將索引堆中的最后一個元素賦值到首位置
* 刪除兩個數組中被移動之前的位置的元素！
* 4. shiftDown操作,維護indexArr與reverseArr
* 5. 返回源數組被移除的元素
*/
public E pop() {
int popIndex = indexArr.get(0);
E temp = array.get(popIndex);
// 1. 刪除原始數組之后论皆，原始數組中的對應的元素
// 向前移動了一個位置，所以對應的索引堆中的指向也得同步修改
for (int i = popIndex + 1; i < indexArr.size(); i++) {
int index = reverseArr.get(i); // 17
indexArr.set(index, indexArr.get(index) - 1);
}
// 2. 移除原始數據中對應的元素
array.remove(popIndex);
// 3 維護一下索引指向數組reverseArr和索引堆indexArr
reverseArr.set(indexArr.get(0), reverseArr.get(indexArr.get(indexArr.size() - 1)));
indexArr.set(0, indexArr.get(indexArr.size() - 1));
reverseArr.remove(popIndex);
indexArr.remove(indexArr.size() - 1);
// 4. shiftDown操作
shiftDown(0, indexArr.size());
// 5. 返回被移除的值
return temp;
}
/** 隨意修改一個數據的優(yōu)先級猾漫，然后維護索引堆
* 根據reverseArr可以快速定位當前索引在
* indexArr的位置点晴，然后將此位置與父與子比較
* 優(yōu)先級，進而確定shiftUp操作或者shiftDown操作
*/
public void setPriority(int i, E e) {
array.set(i, e);
// 找到i對應的索引堆的位置
int index = reverseArr.get(i);
// 找到對應的父節(jié)點
int parent = parent(index);
if(parent != index && compare.compare(array.get(indexArr.get(index)), array.get(indexArr.get(parent))) > 0) {
shiftUp(index);
} else {
shiftDown(index, indexArr.size());
}
}
/** 為一個數組快速建立一個索引堆
* 找到二叉堆最后一個還有子節(jié)點的位置悯周，倒敘
* 節(jié)點粒督，每個節(jié)點進行shiftDown操作！
*/
public void heapify(ArrayList<E> arr){
this.array = arr;
this.indexArr = new ArrayList<>();
this.reverseArr = new ArrayList<>();
int n = 0;
int m = 0;
for (E e : this.array) {
this.indexArr.add(n++);
this.reverseArr.add(m++);
// 這里的m之前寫的是n++和n,程序老是報錯禽翼，
// 查了好久屠橄，居然犯這種低級錯誤！教訓叭虻病锐墙！
}
int last = parent(indexArr.size() - 1);
for (int i = last; i >= 0; i--) {
shiftDown(i, indexArr.size());
}
}
@Override
public String toString() {
return array.toString();
}
}
- 測試類
import java.util.ArrayList;
import java.util.Random;
public class Main {
public static void main(String[] args) {
//addPopP();
heapify();
}
public static void addPopP() {
IndexHeap<Integer> myHeap = new IndexHeap<>((a, b) -> a - b);
Random random = new Random();
int n = 10000;
for (int i = 0; i < n; i++) {
myHeap.add(random.nextInt(10000));
}
for (int i = 0; i < 100; i++) {
myHeap.setPriority(random.nextInt(n), random.nextInt(10000000));
}
Integer first = myHeap.pop();
while (!myHeap.isEmpty()){
int cur = myHeap.pop();
if(cur > first)
throw new IllegalArgumentException("很抱歉，出錯了!");
}
System.out.println("完美长酗！");
}
public static void heapify() {
ArrayList<Integer> arrayList = new ArrayList<>();
IndexHeap<Integer> myHeap = new IndexHeap<>((a, b) -> a - b);
Random random = new Random();
int n = 10000;
for (int i = 0; i < n; i++) {
arrayList.add(random.nextInt(100000000));
}
myHeap.heapify(arrayList);
Integer first = myHeap.pop();
while (!myHeap.isEmpty()){
int cur = myHeap.pop();
if(cur > first)
throw new IllegalArgumentException("很抱歉溪北，出錯了!");
}
System.out.println("完美！");
}
}
