摘要堆可以分为大顶堆和小顶堆，是根据节点与子节点的比较来界定文章中可以使用数组来存放元素，并处理节点与子节点的比较和交换，就是利用了二叉树的基础性质，看完文章相当于再次温习了二叉树的基础性质，今天小编就来说说关于学习数据结构与算法的基础?下面更多详细答案一起来看看吧!

学习数据结构与算法的基础（数据结构与算法-基础）

学习数据结构与算法的基础

摘要

堆可以分为大顶堆和小顶堆，是根据节点与子节点的比较来界定。文章中可以使用数组来存放元素，并处理节点与子节点的比较和交换，就是利用了二叉树的基础性质，看完文章相当于再次温习了二叉树的基础性质。

堆可以分为大顶堆和小顶堆，大顶堆的定义就是每个节点的值都大于或等于其左右子节点的值。小顶堆和大顶堆相反，即每个节点的值都小于或等于其左右子节点的值。接下来的说明以大顶堆为例。

根据大顶堆的定义可以梳理出这几点特性：

  1. 根节点的值是最大的
  2. 节点的左右子节点没有左子节点值必须小于右子节点值，反之也是没有限制
  3. 节点、它的左子节点、它的右子节点这三个节点中，节点的值是最大的

接下来，咱就用数组来实现大顶堆的数据结构。为什么要用数组而不是二叉树来实现？带着问题，继续往下看，后面给出答案。

首先创建一个大顶堆的类结构，并定义数组、数量等属性

public class BinaryHeap<E> { private E[] elements; private int size; }

假设将 elements 数组里 index 索引中的元素放到合适的位置，这时就要考虑两点：

  1. index 索引位置在叶子节点
  2. index 索引位置在非叶子节点

如果是情况1，那就可以不做处理，因为依据特性2来看，子节点之间没有比较元素的要求，凡是叶子节点，都是子节点，所以叶子节点可以不用处理，等着它的父节点来主动比较。

如果是情况2，那么就需要和它的左右子节点比较，然后和最大值的节点交换，在编写逻辑之前，首先要确定以下几点（假定节点的索引为 index，数组中元素的数量为 size）：

  • 非叶子节点的数量 half = size >> 1（half = size / 1）；
  • 节点的左子节点索引 leftIndex = (index << 1) 1；
  • 节点的右子节点索引 rightIndex = leftIndex 1；

位运算符示例：

x << 1: x *2

x >> 1: x / 2

上面这 3 点都是二叉树的基本特性，可以看第六期再温习一下，下面就可以编写防治 index 索引的节点的代码：

private void siftDown(int index) { E element = elements[index]; int half = size >> 1; // 取出非叶子节点 // 第一个叶子结点的索引 == 非叶子节点的数量 // 必须保证 index 是非叶子节点 while (index < half) { // index 的节点有2种情况 // 1、只有左子节点 // 2、同时有左右子节点 // 默认左子节点跟它进行比较 int childIndex = (index << 1) 1; E child = elements[childIndex]; // 右子节点 int rightIndex = childIndex 1; // 保证右子节点存在（rightIndex < size），并比较左右子节点 if (rightIndex < size && compare(elements[rightIndex], child) > 0) { child = elements[ childIndex = rightIndex]; } if (compare(child, element) < 0) break; // 将子节点存放到index位置 elements[index] = child; // 重新设置 index，继续判断 index = childIndex; } elements[index] = element; }

看 siftDown 方法的实现逻辑，可以发现是从 index 往下过滤，寻找合适的位置，那么有没有从 index 往上过滤呢？上代码：

private void siftUp(int index) { E e = elements[index]; while (index > 0) { // 得到 index 位置节点的父节点 int pIndex = (index - 1) >> 1; E p = elements[pIndex]; // 节点小于或等于它的父节点时，结束 if (compare(e, p) <= 0) break; // 交换节点元素，父节点设置为 index 节点再进行判断 elements[index] = p; index = pIndex; } elements[index] = e; }

(index - 1) >> 1 就是获取父节点索引代码，也是二叉树的基本性质。

当解决将 index 索引节点放在合适位置的核心问题之后，就可以处理后面这几个需求了。

比如，当需要批量添加元素，即直接将一个数组处理成大顶堆时（假设元素已经放入 elements 中 ）：

// 批量建堆 private void heapify() { // 自下而上的下滤，只需要处理非叶子节点即可 for (int i = (size >> 1) - 1; i >= 0; i--) { siftDown(i); } }

如果使用 siftUp 函数来实现批量建堆，就需要从头遍历到最后的位置：

// 批量建堆 private void heapify() { // 自上而下的上滤 for (int i = 0; i < size; i ) { siftUp(i); } }

总结：

  • 大顶堆就是每个节点都大于它的左右子节点，小顶堆刚相反；
  • 非叶子节点的数量 half = size >> 1（half = size / 1）；
  • siftDown 来批量建堆时，可以减少一半的遍历次数；

,