java中的最小堆
概述
最小堆minHeap指的级别n的每个节点存储的值小于或等于级别n+1的子节点的值。因此，根就存储了其中最小的值。
注意节点的值与其他兄弟节点的值之间没有必然关系。
java中最小堆的表示
利用数组
常用的是利用数组minHeap[]表示，将最小堆的节点或值存储在数组中。
然后利用公式访问父节点、右子节点、左子节点。根节点索引i=0
- 父节点minHeap[(i-1)/2]
- 右子节点minHeap[(i*2)+2]
- 左子节点minHeap[(i*2)+1]
使用优先队列实现
使用PriorityQueue实现，当从优先队列中添加元素的时候，默认构建的是最小堆。
优先队列中的常见操作：
- add()
- remove()
- peek()检索但不删除队列头，如果为空返回null
- poll()检索并移除队列头
- contains()
- size()返回元素数
java中的最小堆示例