数据结构-堆
插入:每次插入的时候,都往最后一个插入,然后使它上浮。
弹出根节点:让根节点元素和尾节点进行交换,然后让现在的根元素下沉
可以用来做堆排序。大顶堆、小顶堆。
public class minHeap {
private LinkedList<Integer> list;
public minHeap() {
list = new LinkedList<>();
list.add(Integer.MIN_VALUE);
}
public void push(int a) {
list.add(a);
FloatIterate(list.size() - 1);
}
public int pop() {
int n = 1;
assert (n > 0 && n < list.size());
int ret = list.get(n);
Collections.swap(list, 1, list.size() - 1);
list.removeLast();
DownRecursion(1);
return ret;
}
private void DownRecursion(int n) {
if (n * 2 > list.size() - 1) {
return;
}
int child;
if (list.size() - 1 == n * 2) child = n * 2;
else child = list.get(n * 2) > list.get(n * 2 + 1) ? n * 2 + 1 : n * 2;
if (list.get(child) < list.get(n))
Collections.swap(list, n, child);
DownRecursion(child);
}
public int size() {
return list.size() - 1;
}
public static void main(String[] args) {
minHeap mh = new minHeap();
int[] a = new int[]{2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
for (int i = 0; i < 10; i++) {
mh.push(a[i]);
}
while (mh.size() > 0) {
System.out.printf("%d ", mh.pop());
}
}
private void FloatRecursion(int n) {
int fatherPos = n / 2;
if (fatherPos == 0) return;
if (list.get(fatherPos) > list.get(n)) {
Collections.swap(list, fatherPos, n);
FloatRecursion(fatherPos);
}
}
private void FloatIterate(int n) {
int fatherPos = n / 2;
while (fatherPos != 0 && (list.get(fatherPos) > list.get(n))) {
Collections.swap(list, fatherPos, n);
n = fatherPos;
fatherPos /= 2;
}
}
}