堆结构
1. 堆的概念
??堆(heap)有最大堆
和最小堆
两种。
Note: 这里的heap跟JVM中的堆并不是一个概念,JVM中的堆涉及的是内存管理方面的知识,而这里所讲最大、最小堆是一种数据结构。
2. 代码实现
??heap的数据结构是完全二叉树,实现树自然想到要用链表,但这里实现heap只需要使用数组就行,其原因在于完全二叉树中当前节点的索引(index)
与父节点索引(parentIndex)
和子节点索引(leftIndex、rightIndex)
存在者一种数学关系。因此本文利用ArrayList实现最常用的插入操作(add)和删除堆顶(removeMin)操作。
import java.util.*;
/**
* heapPriorityQueue
*/
public class heapPriorityQueue {
private ArrayList list = new ArrayList<>();
private int parent(int index) {
return (index - 1) / 2;
}
private int left(int index) {
return index * 2 + 1;
}
private int right(int index) {
return index * 2 + 2;
}
private boolean hasLeft(int index) {
return left(index) < list.size();
}
private boolean hasRight(int index) {
return right(index) < list.size();
}
private void swap(int index1, int index2) {
int temp = list.get(index1);
list.set(index1, list.get(index2));
list.set(index2, temp);
}
/***
* upheap
*/
private void upheap(int index) {
while (index > 0) {
int p = parent(index);
if (list.get(index) >= list.get(p))
break;
swap(index, p);
index = p;
}
}
/**
* downheap
* 沿着较小的孩子路径下沉, 因此需要判断左、右孩子哪个元素较小
*/
private void downheap(int index) {
while (hasLeft(index)) {
int leftIndex = left(index);
int tempIndex = leftIndex;
if (hasRight(index)) {
int rightIndex = right(index);
if (list.get(leftIndex) > list.get(rightIndex)) {
tempIndex = rightIndex;
}
}
if (list.get(tempIndex) >= list.get(index))
break;
swap(index, tempIndex);
index = tempIndex;
}
}
/**
* check if the list is empty.
*/
public void CheckEmpty() {
if (list.isEmpty()) {
throw new IndexOutOfBoundsException("List is Empty!");
}
}
/**
* 使用ArrayList的好处就在于不需要判断数组边界了
*/
public void add(int value) {
list.add(value);
upheap(list.size() - 1);
}
/**
* remove the minimum(top) element.
*/
public int removeMin() {
CheckEmpty(); // check list size
int min = list.get(0);
swap(0, list.size() - 1); // 1、数组首尾元素对调
list.remove(list.size() - 1); // 2、移除末尾元素(minimum)
downheap(0); // 3、执行下沉操作
return min;
}
}