Last active
August 26, 2020 07:43
-
-
Save zhanglintc/7d3a3418dcf09b4df51871caa0014ad5 to your computer and use it in GitHub Desktop.
Heap
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class BigHeap { | |
// 大根堆, 大顶堆, 最大堆 | |
int capacity = 0; // 容量 | |
int size = 0; // 当前大小 | |
int[] hp; // 数组模拟堆, 本实现使用数组下标 0 位置 | |
public BigHeap(int k) { | |
capacity = k; | |
hp = new int[capacity]; | |
} | |
public int size() { | |
return size; | |
} | |
public int getTop() { | |
return hp[0]; | |
} | |
public int[] getHeap() { | |
return hp; | |
} | |
public void push(int n) { | |
if (capacity == 0) return; // capacity 为 0, 无法 push | |
if (size < capacity) { | |
// 未满, 直接放到末尾, 并作上浮 | |
hp[size++] = n; | |
floatUp(size - 1); | |
} | |
else { | |
// 已满 | |
if (n <= hp[0]) { | |
// 小于堆顶则 pop, 然后 push | |
pop(); | |
push(n); | |
} | |
} | |
} | |
public int pop() { | |
int top = hp.length > 0 ? hp[0] : -1; | |
swap(0, size - 1); // 交换堆顶和末尾 | |
size--; | |
sinkDown(0); // 将堆顶下沉 | |
return top; | |
} | |
private void swap(int a, int b) { | |
int t = hp[a]; | |
hp[a] = hp[b]; | |
hp[b] = t; | |
} | |
private void floatUp(int child) { | |
if (child == 0) return; | |
int farther = (child - 1) / 2; | |
if (hp[child] <= hp[farther]) return; // 不大于父节点, 无需上浮 | |
swap(farther, child); | |
floatUp(farther); | |
} | |
private void sinkDown(int farther) { | |
int left = farther * 2 + 1; | |
int right = (farther + 1) * 2; | |
int maxChild; | |
if (left >= size) return; // 左节点已溢出, 直接返回 | |
if (right < size) maxChild = hp[left] > hp[right] ? left : right; // 右节点未溢出, 取左右值较大者的下标 | |
else maxChild = left; // 右节点溢出, 直接取左节点 | |
if (hp[farther] >= hp[maxChild]) return; // 父节点不小于子节点, 无需下沉 | |
else swap(farther, maxChild); | |
sinkDown(maxChild); // 递归下沉, 直到满足跳出条件 | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class SmallHeap { | |
// 小根堆, 小顶堆, 最小堆 | |
int capacity = 0; // 容量 | |
int size = 0; // 当前大小 | |
int[] hp; // 数组模拟堆, 本实现使用数组下标 0 位置 | |
public SmallHeap(int k) { | |
capacity = k; | |
hp = new int[capacity]; | |
} | |
public int size() { | |
return size; | |
} | |
public int getTop() { | |
return hp[0]; | |
} | |
public int[] getHeap() { | |
return hp; | |
} | |
public void push(int n) { | |
if (capacity == 0) return; // capacity 为 0, 无法 push | |
if (size < capacity) { | |
// 未满, 直接放到末尾, 并作上浮 | |
hp[size++] = n; | |
floatUp(size - 1); | |
} | |
else { | |
// 已满 | |
if (n >= hp[0]) { | |
// 小于堆顶则 pop, 然后 push | |
pop(); | |
push(n); | |
} | |
} | |
} | |
public int pop() { | |
int top = hp.length > 0 ? hp[0] : -1; | |
swap(0, size - 1); // 交换堆顶和末尾 | |
size--; | |
sinkDown(0); // 将堆顶下沉 | |
return top; | |
} | |
private void swap(int a, int b) { | |
int t = hp[a]; | |
hp[a] = hp[b]; | |
hp[b] = t; | |
} | |
private void floatUp(int child) { | |
if (child == 0) return; | |
int farther = (child - 1) / 2; | |
if (hp[child] >= hp[farther]) return; // 不小于父节点, 无需上浮 | |
swap(farther, child); | |
floatUp(farther); | |
} | |
private void sinkDown(int farther) { | |
int left = farther * 2 + 1; | |
int right = (farther + 1) * 2; | |
int minChild; | |
if (left >= size) return; // 左节点已溢出, 直接返回 | |
if (right < size) minChild = hp[left] < hp[right] ? left : right; // 右节点未溢出, 取左右值较小者的下标 | |
else minChild = left; // 右节点溢出, 直接取左节点 | |
if (hp[farther] <= hp[minChild]) return; // 父节点不大于子节点, 无需下沉 | |
else swap(farther, minChild); | |
sinkDown(minChild); // 递归下沉, 直到满足跳出条件 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment