山西建设工程协会网站,禅城区网站建设公司,天河建设网站制作,津南网站建设提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言二叉堆#xff08;Binary Heap#xff09;没什么神秘#xff0c;性质比二叉搜索树 BST 还简单。其主要操作就两个#xff0c;sink#xff08;下沉#xf… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言二叉堆Binary Heap没什么神秘性质比二叉搜索树 BST 还简单。其主要操作就两个sink下沉和 swim上浮用以维护二叉堆的性质。其主要应用有两个首先是一种排序方法「堆排序」第二是一种很有用的数据结构「优先级队列」 一、二叉堆 前言
二叉堆Binary Heap没什么神秘性质比二叉搜索树 BST 还简单。其主要操作就两个sink下沉和 swim上浮用以维护二叉堆的性质。其主要应用有两个首先是一种排序方法「堆排序」第二是一种很有用的数据结构「优先级队列」
一、二叉堆
public class MaxPQKey extends ComparableKey {// 存储元素的数组private Key[] pq;// 当前 Priority Queue 中的元素个数private int size 0;public MaxPQ(int cap) {// 索引 0 不用所以多分配一个空间pq (Key[]) new Comparable[cap 1];}/* 返回当前队列中最大元素 */public Key max() {return pq[1];}/* 插入元素 e */public void insert(Key e) {...}/* 删除并返回当前队列中最大元素 */public Key delMax() {...}/* 上浮第 x 个元素以维护最大堆性质 */private void swim(int x) {...}/* 下沉第 x 个元素以维护最大堆性质 */private void sink(int x) {...}/* 交换数组的两个元素 */private void swap(int i, int j) {Key temp pq[i];pq[i] pq[j];pq[j] temp;}/* pq[i] 是否比 pq[j] 小 */private boolean less(int i, int j) {return pq[i].compareTo(pq[j]) 0;}/* 还有 left, right, parent 三个方法 */public class MaxPQ Key extends ComparableKey {// 为了节约篇幅省略上文给出的代码部分...private void swim(int x) {// 如果浮到堆顶就不能再上浮了while (x 1 less(parent(x), x)) {// 如果第 x 个元素比上层大// 将 x 换上去swap(parent(x), x);x parent(x);}}public class MaxPQ Key extends ComparableKey {// 为了节约篇幅省略上文给出的代码部分...private void sink(int x) {// 如果沉到堆底就沉不下去了while (left(x) size) {// 先假设左边节点较大int max left(x);// 如果右边节点存在比一下大小if (right(x) size less(max, right(x)))max right(x);// 结点 x 比俩孩子都大就不必下沉了if (less(max, x)) break;// 否则不符合最大堆的结构下沉 x 结点swap(x, max);x max;}}public class MaxPQ Key extends ComparableKey {// 为了节约篇幅省略上文给出的代码部分...public void insert(Key e) {size;// 先把新元素加到最后pq[size] e;// 然后让它上浮到正确的位置swim(size);}public class MaxPQ Key extends ComparableKey {// 为了节约篇幅省略上文给出的代码部分...public Key delMax() {// 最大堆的堆顶就是最大元素Key max pq[1];// 把这个最大元素换到最后删除之swap(1, size);pq[size] null;size--;// 让 pq[1] 下沉到正确位置sink(1);return max;}
}}}}}
