最大堆和最小堆

最大堆和最小堆

堆的特性

必须是完全二叉树用数组实现任一结点的值是其子树所有结点的最大值或最小值

最大值时，称为“最大堆”，也称大顶堆；最小值时，称为“最小堆”，也称小顶堆。

最大堆:

最小堆：

对于堆（Heap）这种数据结构，从根节点到任意结点路径上所有的结点都是有序的

堆的实现

在堆中，一般将数组第一个元素赋值为null，不用数组第一位，所以

根节点：n左子树则为：2*n右子树则为：2*n+1对于任一结点n,其父结点为n/2 取整即可。

基于数组实现堆

//基于数组实现的完全二叉树 //如果结点值为n,那么其左子树则为2n,右子树为2n+1；对于任一结点n,其父结点为n/2 取整即可。 List list; public MaxHeap() { //基于数组实现 list = new ArrayList<>(); //数组首位为null，使得数组从下标为1的位置开始， // 这样，完全二叉树中，如果结点值为n,那么其左子树则为2n,右子树为2n+1 list.add(0, null); }

最大堆

所谓最大堆，就是数组中最大的元素位于树的根节点位置，父节点大于子节点，但是，左右子节点大小与左子树还是右子树无关

构建最大堆：

插入新元素到完全二叉树最右子节点即数组尾部上滤不断上滤交换位置，完成插入

何为上滤？

上滤：是将子节点和父节点进行比较，根据条件交换子节点和父节点

在最大堆中：如果子节点比父节点大，则交换，将大的元素上升上去在最小堆中：如果子节点比父节点小，则交换，将小的元素升上去

构建最大堆

/** * 插入堆 *

1. 插入到完全二叉树的右子树

*

2. 上滤：和父节点比较，比父节点大则交换位置

*

3. 不断交换，完成插入

* * @param x */ public void insert(int x) { //插入到数组末，相当于插入到完全二叉树的最右子树 list.add(x); //获得当前插入节点的数组下标,是从 1 开始计 int index = list.size() - 1; //该节点的父节点下标 int pIndex = index / 2; //上滤 while (index > 1) { //最大堆：如果当前节点比父节点值要大，则交换 if (x > list.get(pIndex)) { list.set(index, list.get(pIndex)); index = pIndex; //下一个父节点 pIndex = index / 2; } else { //小则不用调整 break; } } // 最终找到index 的位置，把值放进去 list.set(index, x); }

最小堆

所谓最小堆，就是数组中最小的元素在树的根节点，跟最大堆相反

构建最小堆：

插入新元素到完全二叉树最右子节点即数组尾部上滤不断上滤交换位置，完成插入

最大堆和最小堆的上滤条件是不一样的，上文也有提到

public void insert(int x) { //添加到数组尾部 list.add(x); //获得当前插入节点的数组下标,是从 1 开始计 int index = list.size() - 1; //该节点的父节点下标 int pIndex = index / 2; //上滤 while (index > 1) { //跟父节点比较 if (list.get(pIndex) > x) { //比父节点小，交换 list.set(index, list.get(pIndex)); index = pIndex; pIndex = pIndex / 2; } else { break; } } //找到位置，赋值 list.set(index, x); }

删除元素

移除堆中元素：

找到要删除的元素将数组末端元素即最右子节点元素和其交换下滤

何为下滤？

下滤：是将子节点和父节点进行比较，根据条件交换子节点和父节点

在最大堆中：如果子节点比父节点小，则交换，将小的元素下降下去在最小堆中：如果子节点比父节点小，则交换，将小的元素降下来

最大堆中删除元素

/** * 移除堆中节点 * * @param x */ public void delete(int x) { //判断堆是否为空堆 if (list.isEmpty()) { return; } //获取该元素下标 int index = list.indexOf(x); //没有该元素 if (index == -1) { return; } //获得数组最后一个元素下标，即完全二叉树中最右子树的下标 int tmp = list.size() - 1; //将要删除的x和tmp交换位置，即用最后一个元素替换被删除的位置 list.set(index, list.get(tmp)); //下滤 //父节点下标 int parent; //index: 当前要删除元素x的下标，会变动 for (parent = index; parent * 2 <= list.size() - 1; parent = index) { //左子树下标 index = parent * 2; //如果存在右子节点，且右子节点大于左子节点，则转向右子节点 if (index < list.size() - 1 && list.get(index) < list.get(index + 1)) { //右子树大，指向右子树 index++; } //此时index指向的是孩子节点中较大的数 //如果父节点比左右子节点都大，则不用交换 if (tmp > list.get(index)) { break; } else { // 子树上移，替换当前结点 list.set(parent, list.get(index)); } } //找到合适位置后，在赋值 list.set(parent, list.get(tmp)); list.remove(list.size() - 1); }

最小堆中删除元素

public void delete(int x) { //判断堆是否是空堆 if (list.isEmpty()) { return; } //判断有无该元素 if (!list.contains(x)) { return; } //该元素下标 int index = list.indexOf(x); //获得数组最后一个元素下标，即完全二叉树中最右子树的下标 int tmp = list.size() - 1; //将要删除的x和tmp交换位置，即用最后一个元素替换被删除的位置 list.set(index, list.get(tmp)); //下滤 //父节点下标 int parent; for (parent = index; parent * 2 < list.size() - 1; parent = index) { //左子节点下标 index = parent * 2; //如果存在右子节点，且右子节点小于左子节点，则转向右子节点 if (index != list.size() - 1 && list.get(index) > list.get(index + 1)) { index++; } //此时index是指向孩子节点中较小值的节点 //如果index指向值小于x，则不用交换 if (x < list.get(index)) { break; } else { //比左右子树大，需要交换位置 list.set(parent, list.get(index)); } } //找到合适位置后，在赋值 list.set(parent, list.get(tmp)); list.remove(list.size() - 1); }

获取最值

最大堆和最小堆的最值都在树的根节点即数组第一位

获取最大堆的最大值

public int getMax() { return list.get(1); }

获取最小堆的最小值

public int getMin() { return list.get(1); }

说完堆的实现，下文会谈及堆的应用

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。