数据结构之堆

向右看齐 2023-02-21 11:42 81阅读 0赞

## 思考 ##

假如需要设计一种数据结构，用来存放整数，要求提供3个接口：

*  添加元素
 *  获取最大值
 *  删除最大值

如果使用动态数组、双向链表和二叉树实现这个数据结构对应的时间复杂度如下表所示：

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>添加元素</th> 
   <th>获取最大值</th> 
   <th>删除最大值</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>动态数组\双向链表</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>有序动态数组\双向链表</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
   <td>全排序有点浪费</td> 
  </tr> 
  <tr> 
   <td>平衡二叉搜索树</td> 
   <td>O(logn)</td> 
   <td>O(logn)</td> 
   <td>O(logn)</td> 
   <td>杀鸡焉用牛刀</td> 
  </tr> 
 </tbody> 
</table>

有没有更优的数据结构？使用堆，可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn)。

## 堆的介绍 ##

堆（Heap）也是一种树状的数据结构（不要跟java内存模型中的“堆空间”混淆），常见的堆实现有：

*  二叉堆（Binary Heap，完全二叉堆）
 *  多叉堆（D-heap、D-ary Heap）
 *  索引堆（Index Heap）
 *  二项堆（Binomial Heap）
 *  斐波那契堆（Fibonacci Heap）
 *  左倾堆（Leftist Heap，左式堆）
 *  斜堆（Skew Heap）

本文中主要介绍的是二叉堆。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]  
堆的性质：任意节点的值总是 ≥（ ≤ ）子节点的值

*  如果任意节点的值总是 ≥ 子节点的值，称为：最大堆、大根堆、大顶堆
 *  如果任意节点的值总是 ≤ 子节点的值，称为：最小堆、小根堆、小顶堆

由此可见，堆中的元素必须具备可比较性（跟二叉搜索树一样）。

## 二叉堆（Binary Heap） ##

二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆。

鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

数组中索引i的规律（n是元素数量）：

*  如果 i = 0 ，它是根节点
 *  如果 i > 0 ，它的父节点的索引为 floor( (i – 1) / 2 )
 *  如果 2i + 1 ≤ n – 1，它的左子节点的索引为 2i + 1
 *  如果 2i + 1 > n – 1 ，它无左子节点
 *  如果 2i + 2 ≤ n – 1 ，它的右子节点的索引为 2i + 2
 *  如果 2i + 2 > n – 1 ，它无右子节点

## 堆的接口设计 ##

public interface Heap<E> { 
    
        int size();
    
        boolean isEmpty();
    
        void clear();
    
        E get();
    
        void add(E e);
    
        E replace(E e);
    
        E remove();
    }

## 堆的数据结构 ##

public class BinaryHeap<E> implements Heap<E> { 
    
        private int size;
    
        private E[] elements;
    
        public static final int DEFAULT_CAPACITY = 10;
    
        private Comparator<E> comparator;
    
        public BinaryHeap() { 
            this(null, null);
        }
    
        public BinaryHeap(Comparator<E> comparator) { 
            this.comparator = comparator;
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        }

## 添加元素 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]

将添加的节点加入到数组最后位置，然后循环执行以下操作（图中的80简称为node）

*  如果 node ＞ 父节点，与父节点交换位置
 *  如果 node ≤ 父节点，或者 node 没有父节点，退出循环

这个过程，叫做上滤（Sift Up），时间复杂度：O(logn)

代码实现如下：

public void add(E e) { 
            elementEmptyCheck(e);
    
            elements[size] = e;
            siftUp(size);
            size++;
        }
    
        private void elementEmptyCheck(E e) { 
            if(null == e) { 
                throw new IllegalArgumentException("Element must not be null");
            }
        }
    
        /** * 从index开始上滤 * @param index */
        private void siftUp(int index) { 
            E element = elements[index];
            while (index > 0) { 
                int parentIndex = index >> 1;
                E parentElement = elements[parentIndex];
    
                if(compare(element, parentElement) <= 0) { 
                    break;
                }
    
                elements[index] = parentElement;
                index = parentIndex;
            }
            elements[index] = element;
        }
    
        private int compare(E e1, E e2) { 
            if(null != comparator) { 
                return comparator.compare(e1, e2);
            }
            return ((Comparable) e1).compareTo(e2);
        }

## 删除元素 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]  
删除的步骤如下

1.  用最后一个节点覆盖根节点
2.  删除最后一个节点
3.  循环执行以下操作（图中的43简称为node）
    
     *  如果 node < 最大的子节点，与最大的子节点交换位置
     *  如果 node ≥ 最大的子节点， 或者 node 没有子节点，退出循环

这个过程，叫做下滤（Sift Down），时间复杂度：O(logn)

删除操作的代码实现如下：

public E remove() { 
    
            int lastIndex = --size;
    
            E element = elements[0];
    
            elements[0] = elements[lastIndex];
            elements[lastIndex] = null;
    
            siftDown(0);
    
            return element;
        }
    
        /** * 从index开始下滤 * @param index */
        private void siftDown(int index) { 
            E element = elements[index];
            int half = size >> 1;
            while (index < half) {  // index必须是非叶子节点
    
                int childIndex = (index << 1) + 1;
                E child = elements[childIndex];
    
                if(childIndex + 1 < size) { 
                    if(compare(child, elements[childIndex + 1]) < 0) { 
                        childIndex = childIndex+1;
                        child = elements[childIndex];
                    }
                }
    
                if(compare(element, child) > 0) { 
                    break;
                }
    
                elements[index] = child;
    
                index = childIndex;
            }
            elements[index] = element;
        }

## 替换元素 ##

用新元素替换最大值（第一个元素），操作过程类似删除。

替换操作的代码实现如下：

@Override
        public E replace(E e) { 
            elementEmptyCheck(e);
    
            if(isEmpty()) { 
                elements[size++] = e;
                return null;
            }
    
            E oldValue = elements[0];
            elements[0] = e;
            siftDown(0);
            return oldValue;
        }

## 构建小顶堆 ##

小顶堆无需新建类，只需要在BinaryHeap的构造方法中，修改一下Comparator的比较策略即可。

可以使用下面的代码构造大顶堆：

BinaryHeap<Integer> binaryHeap = new BinaryHeap<>((o1, o2) -> o1 - o2);

可以使用下面的代码构造小顶堆：

BinaryHeap<Integer> binaryHeap = new BinaryHeap<>((o1, o2) -> o2 - o1);

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630111500972.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020063011151458.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200630111532225.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020063011155695.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg