AI 助理
备案控制台
开发者社区 人工智能 文章 正文

《恋上数据结构第1季》二叉堆原理及实现、最小堆解决 TOP K 问题

2022-05-25 149
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《恋上数据结构第1季》二叉堆原理及实现、最小堆解决 TOP K 问题
数据结构与算法笔记目录： 《恋上数据结构》 笔记目录

想加深 Java 基础推荐看这个： Java 强化笔记目录

我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

堆（Heap）

堆的出现

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

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

用已学过的数据结构来对比一下时间复杂度：
在这里插入图片描述
为了迎合此需求出现了一种新的数据结构 —— 堆：

  • 获取最大值：$O(logn)$
  • 删除最大值：$O(logn)$
  • 添加元素：$O(logn)$

堆简介

堆（Heap）是一种 树状 的数据结构，常见的堆实现有

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

堆的重要性质：任意节点的值总是 $\geq$ （ $\leqslant$） 子节点的值

  • 如果任意节点的值总是 $\geq$ 子节点的值，称为：最大堆、大根堆、大顶堆
  • 如果任意节点的值总是 $\leqslant$ 子节点的值，称为：最小堆、小根堆、小顶堆

堆中的元素必须具备可比较性（跟二叉搜索树)一样）
在这里插入图片描述

二叉堆（Binary Heap）

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

鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可
在这里插入图片描述
索引 i 的规律（n 是元素数量）

  • 如果 i = 0，它是 根 节点
  • 如果 i > 0，它的 父 节点的索引为 floor( (i - 1) / 2 )
  • 如果 $2i + 1 \leqslant n - 1$，它的左子节点的索引为 $2i + 1$
  • 如果 $2i + 1 >n - 1$，它无左子节点
  • 如果 $2i + 2 \leqslant n - 1$，它的右子节点的索引为 $2i + 1$
  • 如果 $2i + 2 > n - 1$，它无右子节点

获取最大值

主要就是检测数组是否不能为空，为空则抛出异常。

public E get() {
    emptyCheck();
    return elements[0];
}
private void emptyCheck() {
    if (size == 0) {
        throw new IndexOutOfBoundsException("Heap is empty");
    }
}

最大堆 — 添加

思路是：

  • 将添加的节点放入数组最后

  • 循环执行上滤操作(Sift Up)，即：

    • 如果 node > 父节点

    与父节点交换位置

    • 如果 node <= 父节点，或者 node 没有父节点

    退出循环

  • 时间复杂度：$O(logn)$

在这里插入图片描述

在这里插入图片描述

/**
 * 最大堆 — 添加
 */
public void add(E element) {
    // 检测传入的元素非空
    elementNotNullCheck(element);
    // 扩容操作，确保容量大于当前元素个数大小
    ensureCapacity(size + 1);
    // 将要添加的元素放到数组最后
    elements[size++] = element;
    // 上滤操作
    siftUp(size - 1);
}
/**
 * 让index位置的元素上滤
 */
private void siftUp(int index) {
    E e = elements[index]; // 要添加的节点
    while (index > 0) { // 直到比较到根结点
        int pindex = (index - 1) >> 1; // 父节点索引
        E p = elements[pindex]; // 添加节点的父节点
        if (compare(e, p) <= 0) return;
        
        // 交换index、pindex位置的内容
        E tmp = elements[index];
        elements[index] = elements[pindex];
        elements[pindex] = tmp;
        
        // 重新赋值index
        index = pindex;
    }
}

最大堆 — 添加优化

和上面的区别在于：

  • 并不是每次==节点的值 > 父节点的值==就直接交换
  • 而是将新添加的节点备份，确定最终位置才放上去

在这里插入图片描述

/**
 * 最大堆 — 添加
 */
public void add(E element) {
    // 检测传入的元素非空
    elementNotNullCheck(element);
    // 扩容操作，确保容量大于当前元素个数大小
    ensureCapacity(size + 1);
    // 将要添加的元素放到数组最后
    elements[size++] = element;
    // 上滤操作
    siftUp(size - 1);
}
/**
 * 让index位置的元素上滤
 */
private void siftUp(int index) {
    E element = elements[index];
    while (index > 0) {
        // 父节点索引 = (子节点索引-1) / 2
        int parentIndex = (index - 1) >> 1;
        E parent = elements[parentIndex];
        if (compare(element, parent) <= 0) break;
        
        // 将父元素存储在index位置
        elements[index] = parent;
        
        // 重新赋值index
        index = parentIndex;
    }
    elements[index] = element;
}

最大堆 — 删除

思路是：

  • 用最后一个节点覆盖根结点
  • 删除最后一个节点

  • 循环执行下滤操作(Sift Down)，即：

    • 如果 node < 最大的子节点
      与最大的子节点交换位置
    • 如果 node >= 最大的子节点，或者 node 没有子节点

    退出循环

  • 时间复杂度：$O(logn)$
  • 交换位置的操作可以像添加那样进行优化

在这里插入图片描述
在这里插入图片描述

/**
 * 最大堆—删除堆顶元素
 */
public E remove() {
    // 检测数组不能为空
    emptyCheck(); 
    // 获取数组最后元素的索引
    int lastIndex = --size;
    // 获取要删除元素的节点
    E root = elements[0];
    elements[0] = elements[lastIndex];
    elements[lastIndex] = null;
    
    siftDown(0); // 下滤操作
    return root;
}
/**
 * 让index位置的元素下滤
 */
private void siftDown(int index) {
    E element = elements[index];
    int half = size >> 1; // 非叶子节点的数量
    // 第一个叶子节点的索引 == 非叶子节点的数量
    // index < 第一个叶子节点的索引
    // 必须保证index位置是非叶子节点
    while (index < half) { 
        // index的节点有2种情况
        // 1.只有左子节点
        // 2.同时有左右子节点
        
        // 默认为左子节点跟它进行比较
        int childIndex = (index << 1) + 1;
        E child = elements[childIndex];
        
        // 右子节点
        int rightIndex = childIndex + 1;
        
        // 选出左右子节点最大的那个
        if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
            child = elements[childIndex = rightIndex];
        }
        
        if (compare(element, child) >= 0) break;

        // 将子节点存放到index位置
        elements[index] = child;
        // 重新设置index
        index = childIndex;
    }
    elements[index] = element;
}

replace

替换堆顶的元素；

public E replace(E element) {
    elementNotNullCheck(element);
    
    E root = null;
    if (size == 0) {
        elements[0] = element;
        size++;
    } else {
        root = elements[0];
        elements[0] = element;
        siftDown(0);
    }
    return root;
}

最大堆 — 批量建堆（Heapify）

  • 自上而下的上滤
  • 自下而上的下滤

自上而下的上滤

在这里插入图片描述

自下而上的下滤

在这里插入图片描述

效率对比

  • 自上而下的上滤时间复杂度：$O(nlogn)$
  • 自下而上的下滤时间复杂度：$O(nlogk)$

在这里插入图片描述

二叉堆源码

堆的基本接口 Heap.java

public interface Heap<E> {
    int size();    // 元素的数量
    boolean isEmpty();    // 是否为空
    void clear();    // 清空
    void add(E element);     // 添加元素
    E get();    // 获得堆顶元素
    E remove(); // 删除堆顶元素
    E replace(E element); // 删除堆顶元素的同时插入一个新元素
}

抽象类 AbstractHeap.java

@SuppressWarnings("unchecked")
public abstract class AbstractHeap<E> implements Heap<E> {
    protected int size;
    protected Comparator<E> comparator;
    
    public AbstractHeap(Comparator<E> comparator) {
        this.comparator = comparator;
    }
    
    public AbstractHeap() {
        this(null);
    }
    
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    
    protected int compare(E e1, E e2) {
        return comparator != null ? comparator.compare(e1, e2) 
                : ((Comparable<E>)e1).compareTo(e2);
    }
}

二叉堆 BinaryHeap.java

/**
 * 二叉堆（最大堆）
 */
@SuppressWarnings("unchecked")
public class BinaryHeap<E> extends AbstractHeap<E> {
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    
    public BinaryHeap(E[] elements, Comparator<E> comparator)  {
        super(comparator);
        
        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }
    
    public BinaryHeap(E[] elements)  {
        this(elements, null);
    }
    
    public BinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }
    
    public BinaryHeap() {
        this(null, null);
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    /**
     * 删除堆顶元素
     */
    public E remove() {
        emptyCheck();
        
        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        
        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        
        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }
    
    /**
     * 批量建堆
     */
    private void heapify() {
        // 自上而下的上滤
//        for (int i = 1; i < size; i++) {
//            siftUp(i);
//        }
        
        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }
    
    /**
     * 让index位置的元素下滤
     * @param index
     */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1; // 非叶子节点的数量
        // 第一个叶子节点的索引 == 非叶子节点的数量
        // index < 第一个叶子节点的索引
        // 必须保证index位置是非叶子节点
        while (index < half) { 
            // index的节点有2种情况
            // 1.只有左子节点
            // 2.同时有左右子节点
            
            // 默认为左子节点跟它进行比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            
            // 右子节点
            int rightIndex = childIndex + 1;
            
            // 选出左右子节点最大的那个
            if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
                child = elements[childIndex = rightIndex];
            }
            
            if (compare(element, child) >= 0) break;

            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }
    
    /**
     * 让index位置的元素上滤
     */
    private void siftUp(int index) {
//        E e = elements[index];
//        while (index > 0) {
//            int pindex = (index - 1) >> 1;
//            E p = elements[pindex];
//            if (compare(e, p) <= 0) return;
//            
//            // 交换index、pindex位置的内容
//            E tmp = elements[index];
//            elements[index] = elements[pindex];
//            elements[pindex] = tmp;
//            
//            // 重新赋值index
//            index = pindex;
//        }
        E element = elements[index];
        while (index > 0) {
            // 父节点索引 = (子节点索引-1) / 2
            int parentIndex = (index - 1) >> 1;
            E parent = elements[parentIndex];
            if (compare(element, parent) <= 0) break;
            
            // 将父元素存储在index位置
            elements[index] = parent;
            
            // 重新赋值index
            index = parentIndex;
        }
        elements[index] = element;
    }
    
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }
    
    private void emptyCheck() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }
    
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
}

构建一个最小堆

在写完最大堆以后，实现最小堆不需要修改源代码，只需要在创建堆时，传入与最大堆比较方式相反的比较器即可。

public static void main(String[] args) {
    Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
    BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2 - o1; // 与最大堆比较方式相反
        }
    });
}

TOP K 问题

什么是 TopK 问题

  • 从 n 个整数中，找出最大的前 k 个数（k << n）
  • 例如：从100万个整数中找出最大的100个整数

TopK 问题的解法之一：可以用数据结构 “堆” 来解决

如果使用排序算法进行全排序，需要 $O(nlogn)$ 的时间复杂度

如果使用二叉堆来解决，可以使用 $O(nlogk)$ 的时间复杂度来解决

  • 新建一个小顶堆

  • 扫描 n 个整数

    • 先将遍历到的前 k 个数放入堆中
    • 从第 k+1 个数开始，如果大于堆顶元素，就使用 replace 操作

    （删除堆顶元素，将第k+1个数添加到堆中）

  • 扫描完毕后，堆中剩下的就是最大的前 k 个数
public static void main(String[] args) {
    // 新建一个小顶堆
    BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    
    // 找出最大的前k个数
    int k = 3;
    Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93, 
            91, 19, 54, 47, 73, 62, 76, 63, 35, 18, 
            90, 6, 65, 49, 3, 26, 61, 21, 48};
    for (int i = 0; i < data.length; i++) {
        if (heap.size() < k) { // 前k个数添加到小顶堆
            heap.add(data[i]); // logk
        } else if (data[i] > heap.get()) { // 如果是第 k + 1 个数，并且大于堆顶元素
            heap.replace(data[i]); // logk
        }
    }
    // O(nlogk)
}

如果是找出最小的前 k 个数呢？

  • 用大顶堆
  • 如果小于堆顶元素，就使用 replace 操作
文章标签：
Java
搜索推荐
索引
算法
关键词：
数据结构堆
数据结构原理
数据结构最小堆
数据结构二叉堆
数据结构实现
萌宅鹿同学
目录
相关文章
进步`于辰
|
1月前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用，详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解，帮助读者理解散列表的工作原理和优化策略。
进步`于辰
38 1
散列表的数据结构以及对象在JVM堆中的存储过程
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
68 16
神明木佑
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
83 1
糜终
|
2月前
|
消息中间件 存储 Java
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
数据结构之 - 深入探析队列数据结构: 助你理解其原理与应用
糜终
40 4
是店小二呀
|
2月前
|
搜索推荐 索引
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（二）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
32 4
是店小二呀
|
2月前
|
搜索推荐 C++
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（一）
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理
是店小二呀
36 4
平凡程序猿~
|
2月前
|
存储 算法 调度
数据结构--二叉树的顺序实现（堆实现）
数据结构--二叉树的顺序实现（堆实现）
平凡程序猿~
70 1
是店小二呀
|
2月前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用：深入探索完全二叉树的独特魅力
是店小二呀
56 1
Dylaniou
|
2月前
|
Java C++
【数据结构】探索红黑树的奥秘：自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理，介绍其五大原则，并通过图解和代码示例展示其内部机制。同时，对比红黑树与二叉查找树的性能差异，帮助读者更好地理解这两种数据结构的特点和应用场景。
Dylaniou
34 0
阿客不是客
|
2月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
26 0