```java
package ds.impl;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MaxPriorityQueue<T> implements Iterable<T> {
private T[] pq;
private int size;
private Comparator<T> comparator;
public MaxPriorityQueue(int capacity, Comparator comparator) {
pq = (T[]) new Object[capacity + 1];
size = 0;
this.comparator = comparator;
}
public MaxPriorityQueue(int capacity) {
this(capacity, null);
}
public MaxPriorityQueue(Comparator comparator) {
this(1, comparator);
}
public MaxPriorityQueue() {
this(1);
}
public MaxPriorityQueue(T[] keys) {
size = keys.length;
pq = (T[]) new Object[size + 1];
System.arraycopy(keys, 0, pq, 1, size);
for (int k = size / 2; k >= 1; k--) {
sink(k);
}
}
public void insert(T key) {
if (size == pq.length - 1) {
resize(2 * pq.length);
}
pq[++size] = key;
swim(size);
}
public T max() {
notEmptyCheck();
return pq[1];
}
public T deleteMax() {
notEmptyCheck();
T result = pq[1];
swap(1, size--);
sink(1);
pq[size + 1] = null;
if ((size > 0) && (size == (pq.length - 1) / 4)) {
resize(pq.length / 2);
}
return result;
}
private void notEmptyCheck() {
if (isEmpty()) {
throw new NoSuchElementException();
}
}
@Override
public Iterator<T> iterator() {
return new HeapIterator();
}
private class HeapIterator implements Iterator<T> {
private MaxPriorityQueue<T> copy;
public HeapIterator() {
if (comparator == null) {
copy = new MaxPriorityQueue<>(size());
} else {
copy = new MaxPriorityQueue<>(size(), comparator);
}
for (int i = 1; i <= size; i++) {
copy.insert(pq[i]);
}
}
@Override
public boolean hasNext() {
return !copy.isEmpty();
}
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return copy.deleteMax();
}
}
private void sink(int k) {
while (2 * k <= size) {
int j = 2 * k;
if (j < size && less(j, j + 1)) {
j++;
}
if (!less(k, j)) {
break;
}
swap(k, j);
k = j;
}
}
private boolean less(int a, int b) {
if (comparator == null) {
return ((Comparable<T>) pq[a]).compareTo(pq[b]) < 0;
} else {
return comparator.compare(pq[a], pq[b]) < 0;
}
}
private void swap(int a, int b) {
T tmp = pq[a];
pq[a] = pq[b];
pq[b] = tmp;
}
private void resize(int capacity) {
T[] tmp = (T[]) new Object[capacity];
for (int i = 1; i <= size; i++) {
tmp[i] = pq[i];
}
pq = tmp;
}
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
swap(k, k / 2);
k = k / 2;
}
}
private boolean isEmpty() {
return size() == 0;
}
private int size() {
return size;
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記