数据结构--堆

堆有两个特性:

  • 堆是一个完全二叉树
  • 堆中所有父节点都大于(最大堆)或者小于(最小堆)子结点。 在一般的实现中,我们可以用数组来存储堆中的元素,数组的索引用于实现结点左右孩子的查找。 最小堆的实现代码如下:
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 
 * 功能描述: 最小堆的实现
 * 
 * @version 2.0.0
 * @author zhiminchen
 */
public class MinHeap<E extends Comparable<E>> {

    // 用于存储数据E对象
    private E[] data;
    // 当前数组已经存储了多少个数据
    private int size;

    public MinHeap(int capacity) {
        data = (E[]) new Comparable[capacity];
        size = 0;
    }

    public MinHeap() {
        this(16);
    }

    /**
     * 传入一个array数组,构造堆
     * 
     * @param array
     */
    public MinHeap(E[] array) {
        data = (E[]) new Comparable[array.length];
        // 将array数据复制到data数组中
        for (int i = 0; i < data.length; i++) {
            data[i] = array[i];
        }
        size = array.length;
        // 对堆中非叶子结点做siftDown操作, 这样堆的特性就维护好了
        for (int i = parent(array.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 
     * 功能描述: 堆是否为空的方法
     * 
     * @return boolean
     * @version 2.0.0
     * @author zhiminchen
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 
     * 功能描述: 返回当前堆的大小
     * 
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    public int size() {
        return size;
    }

    /**
     * 
     * 功能描述: 得到index的父亲结点
     * 
     * @param index
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    private int parent(int index) {
        if (index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    /**
     * 
     * 功能描述: 得到index的左孩子结点
     * 
     * @param index
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    private int left(int index) {
        return 2 * index + 1;
    }

    /**
     * 
     * 功能描述: 得到index下的右孩子结点
     * 
     * @param index
     * @return int
     * @version 2.0.0
     * @author zhiminchen
     */
    private int right(int index) {
        return 2 * index + 2;
    }

    /**
     * 
     * 功能描述: 往堆中增加元素element
     * 
     * @param element void
     * @version 2.0.0
     * @author zhiminchen
     */
    public void add(E element) {
        if (size >= data.length) {
            resize(data.length * 2);
        }

        data[size] = element;

        siftUp(size);
        size++;
    }

    /**
     * 
     * 功能描述: 删除堆顶的元素,并返回
     * 
     * @return E
     * @version 2.0.0
     * @author zhiminchen
     */
    public E remove() {
        if (size <= 0) {
            return null;
        }
        E ret = data[0];
        // 将数组的最后一个元素放到队列的头
        data[0] = data[size - 1];
        data[size - 1] = null;
        // 对size进行维护
        size--;
        // 对零位的数据进行下沉操作, 以保持堆的特性
        siftDown(0);
        return ret;
    }

    /**
     * 
     * 功能描述: 查看堆中最小的元素
     * 
     * @return E
     * @version 2.0.0
     * @author zhiminchen
     */
    public E findMin() {
        if (size == 0)
            throw new IllegalArgumentException("Can not findMin when heap is empty.");
        return data[0];
    }

    /**
     * 
     * 功能描述: 对index的元素进行下沉操作,以保持推的特性
     * 
     * @param index void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void siftDown(int index) {
        int left = left(index);
        // 递归退出条件 left>=size说明当前节点已经是叶子节点了
        if (left >= size) {
            return;
        }
        // 假设index的左节点是最小的节点
        E min = data[left];
        // 如果index节点有右孩子并且右孩子比左孩子还小, index结点需要跟最小的节点进行交换
        if (left + 1 < size && min.compareTo(data[left + 1]) > 0) {
            min = data[left + 1];
            left = left + 1;
        }
        // 当index节点的数据比最小的节点还大的时候,则进行交换,否则结束
        if (data[index].compareTo(min) > 0) {
            swap(index, left);
            siftDown(left);
        }
    }

    /**
     * 
     * 功能描述: 对index元素进行上浮操作, 以维持队的特性
     * 
     * @param size2 void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void siftUp(int index) {
        // 递归退出的条件
        if (index <= 0) {
            return;
        }
        // index节点比父亲节点小, 则进行上浮
        if (data[index].compareTo(data[parent(index)]) < 0) {
            swap(index, parent(index));
            // 递归调用,继续上浮
            siftUp(parent(index));
        }
    }

    /**
     * 
     * 功能描述: 交换索引为a, b的数据
     * 
     * @param a
     * @param b void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void swap(int a,
                      int b) {
        E temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }

    /**
     * 
     * 功能描述: 对堆进行扩容
     * 
     * @param capacity void
     * @version 2.0.0
     * @author zhiminchen
     */
    private void resize(int capacity) {
        E[] temp = (E[]) new Object[capacity];
        for (int i = 0; i < data.length; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("heap size : %d capacity : %d ", size, data.length));
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        Random random = new Random();
        int n = 100;
        Integer array[] = new Integer[n];
        for (int i = 0; i < 100; i++) {
            array[i] = random.nextInt(Integer.MAX_VALUE);
        }

        MinHeap<Integer> heap = new MinHeap<Integer>(array);

        System.out.println(heap);

        List<Integer> list = new ArrayList<Integer>();
        while (!heap.isEmpty()) {
            list.add(heap.remove());
        }

        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1) > list.get(i)) {
                throw new RuntimeException();
            }
        }

    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Netty ByteBuf源码解读

      Netty里的ByteBuf主要用于发送或接收消息。在JDK里有相似功能的类java.nio.ByteBuffer。由于JDK在设计ByteBuffer A...

    良辰美景TT
  • 数据结构--线段树

      线段树用于处理区间数据的更新与查询问题,不考虑往区间中增加与删除数据的,主要用于统计数据方面的需求,在更新与查询的时间复杂度都为logn级别。线段树不属...

    良辰美景TT
  • Spring Cloud Config

      每个系统都会有一些配置信息需要处理,比如通用的数据源的配置,连接池的配置,log信息的配置。原来系统的处理方式都是通过将配置文件打包部署到线上,对于需要动态...

    良辰美景TT
  • 归并排序

    归并排序是典型的分而治之策略的应用。主要是把一个数组分成若干个子数组进行从小到大的归并直至有序。下面所说的归并排序默认为2路归并排序。

    AI那点小事
  • Centos7 YUM安装MariaDB 10.0

    明哥的运维笔记
  • Centos7 YUM安装MariaDB 10.0

    明哥的运维笔记
  • JAVA 用数组实现 ArrayList

      我们知道 ArrayList 是一个集合,它能存放各种不同类型的数据,而且其容量是自动增长的。那么它是怎么实现的呢?   其实 ArrayList 的底层是...

    IT可乐
  • 简单排序

    排序是数据处理中十分常见且核心的操作,虽说实际项目开发中很小几率会需要我们手动实现,毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我...

    AI那点小事
  • 最小堆与索引堆

    我们先来完成一个最小堆,采用JDK的ArrayList作为底层数据结构。关于堆的概念请参考数据结构整理 中最大堆的部分

    算法之名
  • 用一个测试类简化排序算法时间复杂度的研究

    在学习算法的过程中,除了熟练掌握各种算法的程序逻辑外,还经常需要用到一些测试案例对算法的时间复杂度做具体的测试。本文将通过打造一个测试类工具包,让我们可以更简便...

    智慧zhuhuix

扫码关注云+社区

领取腾讯云代金券