数据结构之二叉堆

二叉堆

堆是一种特别的二叉树,满足以下条件的二叉树,可以称之为堆:

  • 完全二叉树;
  • 每一个节点的值都必须 大于等于或者小于等于 其孩子节点的值。

堆具有以下的特点:

  • 可以在 O(logN) 的时间复杂度内向堆中插入元素;
  • 可以在 O(logN) 的时间复杂度内向堆中删除元素;
  • 可以在 O(1)的时间复杂度内获取堆中的最大值或最小值。

堆的分类

堆有两种类型:最大堆和最小堆。

  • 最大堆:堆中每一个节点的值都大于等于其孩子节点的值。所以最大堆的特性是 堆顶元素(根节点)是堆中的最大值。
  • 最小堆:堆中每一个节点的值都小于等于其孩子节点的值。所以最小堆的特性是 堆顶元素(根节点)是堆中的最小值。

在这里插入图片描述

PriorityQueue

在Java中的堆可以使用 java.util 包下的优先队列 PriorityQueue 类来表示。

//创建一个空的最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
//创建一个空的最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 创建带初始值的「堆」, 或者称为「堆化」操作
PriorityQueue<Integer> heapWithValues= new PriorityQueue<>(Arrays.asList(3,1,2));

//插入元素
minHeap.add(1);
maxHeap.add(1);
//获取堆顶元素
minHeap.peek();//最小值
maxHeap.peek();//最大值
//删除堆顶元素
minHeap.poll();
maxHeap.poll();
//获取堆的长度
minHeap.size();
maxHeap.size();
//判断堆是否存在元素,若存在返回false,不存在返回true
minHeap.isEmpty();
maxHeap.isEmpty();

基本用法

public class Demo_01_PriorityQueue {
    public static void main(String[] args) {
        //堆化[5,7,8]
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> b - a);
        minHeap.add(8);
        minHeap.add(7);
        minHeap.add(1);
        minHeap.add(3);
        minHeap.add(9);
        // 添加元素,add方法是通过调用offer方法添加元素的
        System.out.println(minHeap.offer(2));
        System.out.println("size:" + minHeap.size());
        System.out.println("toString:" + minHeap.toString());
        // 判断堆是否为空
        System.out.println("isEmpty:" + minHeap.size());
        // 获取堆顶元素
        System.out.println("peek:" + minHeap.peek());
        // 删除元素
        System.out.println("poll:" + minHeap.poll());
        // 获取堆的比较器对象
        System.out.println(minHeap.comparator());
        // 查找堆中是否存在元素 6
        System.out.println("contains:" + minHeap.contains(6));
        // 将堆转换成一个对象数组
        Object[] array = minHeap.toArray();
        System.out.println(Arrays.toString(array));
    }
}

时间复杂度和空间复杂度分析

堆的用法时间复杂度空间复杂度
创建堆O(N)O(N)
插入元素O(logN)O(1)
获取堆顶元素O(1)O(1)
删除堆顶元素O(logN)O(1)
获取堆的长度O(1)O(1)

自定义堆

初始化堆

// 数组创建完全二叉树的结构
private int[] maxHeap;
// 数组总大小
private int size;
// 记录堆的元素个数
private int count;
// 默认堆大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;

// 默认初始化堆大小
public MaxHeap() {
    this(DEFAULT_INITIAL_CAPACITY);
}

// 初始化
public MaxHeap(int size) {
    this.size = size;
    this.maxHeap = new int[size + 1];
    // 第1个元素不使用,随便赋值
    maxHeap[0] = -1;
}
/**
  * 交换值
  *
  * @param arr 堆
  * @param a   a元素的索引
  * @param b   b元素的索引
  */
private void swap(int[] arr, int a, int b) {
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
}

插入元素

/**
  * 插入元素
  *
  * @param e 元素
  * @return 成功返回true,失败返回false
  */
public boolean add(int e) {
    return offer(e);
}
public boolean offer(int e) {
    // 堆元素加1
    count++;
    // 堆中元素的个数大于初始化数组的个数
    if (count > size) {
        count--;
        return false;
    }
    // 添加元素
    maxHeap[count] = e;
    // 新增元素的索引位置
    int index = count;
    /**
      * 注意,若用数组表示完全二叉树,并且根结点存储在数组的【索引1】的位置的时
      * 任何一个节点的父节点索引位置为【该节点的索引位置/2】,任何一个节点的左孩
      * 子节点的索引位置为【该节点的索引位置*2】,任何一个节点的右孩子节点的索引
      * 位置为【该节点的索引位置*2+1】;
      */
    // 新增元素的父节点的索引位置
    int parent = index >>> 1;
    // 当添加的元素大于父节点时,将父节点的值和新增元素的值交换
    while (index > 1 && maxHeap[index] > maxHeap[parent]) {
        // 交换
        swap(maxHeap, index, parent);
        // 元素上浮
        index = parent;
        parent = index >>> 1;
    }
    return true;
}

获取堆顶元素

/**
  * 获取堆顶元素
  *
  * @return 返回堆顶元素
  */
public int peek() {
    return maxHeap[1];
}

删除堆顶元素

/**
  * 删除堆顶元素
  *
  * @return 返回被删除的元素
  */
public int poll() {
    // 返回结果
    int result = 0x80000000;
    // 堆个数为0
    if (count <= 0) {
        return result;
    } else { // 堆个数至少为1
        result = maxHeap[1];
        // 将堆中最后一个元素替换到堆顶
        maxHeap[1] = maxHeap[count];
        // 堆中元素减1
        count--;
        // 被删除元素索引
        int index = 1;
        // 若删除的节点是根节点
        while (index < count && index <= (count >>> 1)) {
            // 被删除节点的左节点和右节点
            int left = 2 * index, right = 2 * index + 1;
            // 当删除节点的元素小于,左节点或右节点,表示该元素值小,此时需要将该元素与左、右孩子节点中最大的进行交换
            if (maxHeap[index] < maxHeap[left] || maxHeap[index] < maxHeap[right]) {
                // 与左、右节点中最大的进行交换
                if (maxHeap[left] > maxHeap[right]) {
                    swap(maxHeap, index, left);
                    // 左元素下沉,记录下沉后索引的位置
                    index = left;
                } else {
                    swap(maxHeap, index, right);
                    // 右元素下沉,同上
                    index = right;
                }
            } else {
                break;
            }
        }
    }
    return result;
}

堆的大小

/**
  * 获取堆的大小
  *
  * @return 返回堆中元素个数
  */
public int size() {
    return count;
}

/**
  * 判断堆是否为空
  *
  * @return 空返回true,非空返回false
  */
public boolean isEmpty() {
    return count == 0;
}

最大堆完整代码

/**
 * Author : AiTao
 * Create : 2021/4/1 22:20
 * Description : 最大堆类
 */
public class MaxHeap {
    // 数组创建完全二叉树的结构
    private int[] maxHeap;
    // 数组总大小
    private int size;
    // 记录堆的元素个数
    private int count;
    // 默认堆大小
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    // 默认初始化堆大小
    public MaxHeap() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    // 初始化
    public MaxHeap(int size) {
        this.size = size;
        this.maxHeap = new int[size + 1];
        // 第1个元素不使用,随便赋值
        maxHeap[0] = 0x80000000;
    }

    /**
     * 插入元素
     *
     * @param e 元素
     * @return 成功返回true,失败返回false
     */
    public boolean add(int e) {
        return offer(e);
    }

    public boolean offer(int e) {
        // 堆元素加1
        count++;
        // 堆中元素的个数大于初始化数组的个数
        if (count > size) {
            count--;
            return false;
        }
        // 添加元素
        maxHeap[count] = e;
        // 新增元素的索引位置
        int index = count;
        /**
         * 注意,如果用数组表示完全二叉树,并且根结点存储在数组的[索引1]的位置的时候,
         * 任何一个节点的父节点索引位置为「该节点的索引位置/2」,任何一个节点的左孩
         * 子节点的索引位置为「该节点的索引位置*2」,任何一个节点的右孩子节点的索引
         * 位置为「该节点的索引位置*2+1」
         */
        // 新增元素的父节点的索引位置
        int parent = index >>> 1;
        // 当添加的元素大于父节点时,将父节点的值和新增元素的值交换
        while (index > 1 && maxHeap[index] > maxHeap[parent]) {
            // 交换
            swap(maxHeap, index, parent);
            // 元素上浮
            index = parent;
            parent = index >>> 1;
        }
        return true;
    }

    /**
     * 获取堆顶元素
     *
     * @return 返回堆顶元素
     */
    public int peek() {
        return maxHeap[1];
    }

    /**
     * 删除堆顶元素
     *
     * @return 返回被删除的元素
     */
    public int poll() {
        // 返回结果
        int result = 0x80000000;
        // 堆个数为0
        if (count <= 0) {
            return result;
        } else { // 堆个数至少为1
            result = maxHeap[1];
            // 将堆中最后一个元素替换到堆顶
            maxHeap[1] = maxHeap[count];
            // 堆中元素减1
            count--;
            // 被删除元素索引
            int index = 1;
            // 若删除的节点是根节点
            while (index < count && index <= (count >>> 1)) {
                // 被删除节点的左节点和右节点
                int left = 2 * index, right = 2 * index + 1;
                // 当删除节点的元素小于,左节点或右节点,表示该元素值小,此时需要将该元素与左、右孩子节点中最大的进行交换
                if (maxHeap[index] < maxHeap[left] || maxHeap[index] < maxHeap[right]) {
                    // 与左、右节点中最大的进行交换
                    if (maxHeap[left] > maxHeap[right]) {
                        swap(maxHeap, index, left);
                        // 左元素下沉,记录下沉后索引的位置
                        index = left;
                    } else {
                        swap(maxHeap, index, right);
                        // 右元素下沉,同上
                        index = right;
                    }
                } else {
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 获取堆的大小
     *
     * @return 返回堆中元素个数
     */
    public int size() {
        return count;
    }

    /**
     * 判断堆是否为空
     *
     * @return 空返回true,非空返回false
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 重写toString
     */
    public String toString() {
        if (count == 0) {
            return "堆为空!";
        } else {
            // 打印 [5,4,3,2,1]
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = 1; i <= count; i++) {
                sb.append(maxHeap[i]);
                if (i != count) {
                    sb.append(',');
                }
            }
            sb.append(']');
            return sb.toString();
        }
    }

    /**
     * 交换值
     *
     * @param arr 堆
     * @param a   a元素的索引
     * @param b   b元素的索引
     */
    private void swap(int[] arr, int a, int b) {
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}

最小堆完整代码

/**
 * Author : AiTao
 * Create : 2021/4/1 22:21
 * Description : 最小堆类
 */
public class MinHeap {
    // 数组创建完全二叉树的结构
    private int[] minHeap;
    // 数组总大小
    private int size;
    // 记录堆的元素个数
    private int count;
    // 默认堆大小
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    // 默认初始化堆大小
    public MinHeap() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    // 初始化
    public MinHeap(int size) {
        this.size = size;
        this.minHeap = new int[size + 1];
        // 第1个元素不使用,随便赋值
        minHeap[0] = 0x7fffffff;
    }

    /**
     * 插入元素
     *
     * @param e 元素
     * @return 成功返回true,失败返回false
     */
    public boolean add(int e) {
        return offer(e);
    }

    public boolean offer(int e) {
        // 堆元素加1
        count++;
        // 堆中元素的个数大于初始化数组的个数
        if (count > size) {
            count--;
            return false;
        }
        // 添加元素
        minHeap[count] = e;
        // 新增元素的索引位置
        int index = count;
        /**
         * 注意,如果用数组表示完全二叉树,并且根结点存储在数组的[索引1]的位置的时候,
         * 任何一个节点的父节点索引位置为「该节点的索引位置/2」,任何一个节点的左孩
         * 子节点的索引位置为「该节点的索引位置*2」,任何一个节点的右孩子节点的索引
         * 位置为「该节点的索引位置*2+1」
         */
        // 新增元素的父节点的索引位置
        int parent = index >>> 1;
        // 当添加的元素大于父节点时,将父节点的值和新增元素的值交换
        while (index > 1 && minHeap[index] < minHeap[parent]) {
            // 交换
            swap(minHeap, index, parent);
            // 元素上浮
            index = parent;
            parent = index >>> 1;
        }
        return true;
    }

    /**
     * 获取堆顶元素
     *
     * @return 返回堆顶元素
     */
    public int peek() {
        return minHeap[1];
    }

    /**
     * 删除堆顶元素
     *
     * @return 返回被删除的元素
     */
    public int poll() {
        // 返回结果
        int result = 0x7fffffff;
        // 堆个数为0
        if (count <= 0) {
            return result;
        } else { // 堆个数至少为1
            result = minHeap[1];
            // 将堆中最后一个元素替换到堆顶
            minHeap[1] = minHeap[count];
            // 堆中元素减1
            count--;
            // 被删除元素索引
            int index = 1;
            // 若删除的节点是根节点
            while (index < count && index <= (count >>> 1)) {
                // 被删除节点的左节点和右节点
                int left = 2 * index, right = 2 * index + 1;
                // 当删除节点的元素小于,左节点或右节点,表示该元素值大,此时需要将该元素与左、右孩子节点中最小的进行交换
                if (minHeap[index] > minHeap[left] || minHeap[index] > minHeap[right]) {
                    // 与左、右节点中最大的进行交换
                    if (minHeap[left] > minHeap[right]) {
                        swap(minHeap, index, left);
                        // 左元素下沉,记录下沉后索引的位置
                        index = left;
                    } else {
                        swap(minHeap, index, right);
                        // 右元素下沉,同上
                        index = right;
                    }
                } else {
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 获取堆的大小
     *
     * @return 返回堆中元素个数
     */
    public int size() {
        return count;
    }

    /**
     * 判断堆是否为空
     *
     * @return 空返回true,非空返回false
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 重写toString
     */
    public String toString() {
        if (count == 0) {
            return "堆为空!";
        } else {
            // 打印 [5,4,3,2,1]
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = 1; i <= count; i++) {
                sb.append(minHeap[i]);
                if (i != count) {
                    sb.append(',');
                }
            }
            sb.append(']');
            return sb.toString();
        }
    }
    
    /**
     * 交换值
     *
     * @param arr 堆
     * @param a   a元素的索引
     * @param b   b元素的索引
     */
    private void swap(int[] arr, int a, int b) {
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}

热门文章

暂无图片
编程学习 ·

Java输出数组的内容

Java输出数组的内容_一万个小时-CSDN博客_java打印数组内容1. 输出内容最常见的方式// List<String>类型的列表List<String> list new ArrayList<String>();list.add("First");list.add("Second");list.add("Third");list.ad…
暂无图片
编程学习 ·

母螳螂的“魅惑之术”

在它们对大蝗虫发起进攻的时候&#xff0c;我认认真真地观察了一次&#xff0c;因为它们突然像触电一样浑身痉挛起来&#xff0c;警觉地面对限前这个大家伙&#xff0c;然后放下自己优雅的身段和祈祷的双手&#xff0c;摆出了一个可怕的姿势。我被眼前的一幕吓到了&#xff0c;…
暂无图片
编程学习 ·

疯狂填词 mad_libs 第9章9.9.2

#win7 python3.7.0 import os,reos.chdir(d:\documents\program_language) file1open(.\疯狂填词_d9z9d2_r.txt) file2open(.\疯狂填词_d9z9d2_w.txt,w) words[ADJECTIVE,NOUN,VERB,NOUN] str1file1.read()#方法1 for word in words :word_replaceinput(fEnter a {word} :)str1…
暂无图片
编程学习 ·

HBASE 高可用

为了保证HBASE是高可用的,所依赖的HDFS和zookeeper也要是高可用的. 通过参数hbase.rootdir指定了连接到Hadoop的地址,mycluster表示为Hadoop的集群. HBASE本身的高可用很简单,只要在一个健康的集群其他节点通过命令 hbase-daemon.sh start master启动一个Hmaster进程,这个Hmast…
暂无图片
编程学习 ·

js事件操作语法

一、事件的绑定语法 语法形式1 事件监听 标签对象.addEventListener(click,function(){}); 语法形式2 on语法绑定 标签对象.onclick function(){} on语法是通过 等于赋值绑定的事件处理函数 , 等于赋值本质上执行的是覆盖赋值,后赋值的数据会覆盖之前存储的数据,也就是on…
暂无图片
编程学习 ·

Photoshop插件--晕影动态--选区--脚本开发--PS插件

文章目录1.插件界面2.关键代码2.1 选区2.2 动态晕影3.作者寄语PS是一款栅格图像编辑软件&#xff0c;具有许多强大的功能&#xff0c;本文演示如何通过脚本实现晕影动态和选区相关功能&#xff0c;展示从互联网收集而来的一个小插件&#xff0c;供大家学习交流&#xff0c;请勿…
暂无图片
编程学习 ·

vs LNK1104 无法打开文件“xxx.obj”

写在前面&#xff1a; 向大家推荐两本新书&#xff0c;《深度学习计算机视觉实战》和《学习OpenCV4&#xff1a;基于Python的算法实战》。 《深度学习计算机视觉实战》讲了计算机视觉理论基础&#xff0c;讲了案例项目&#xff0c;讲了模型部署&#xff0c;这些项目学会之后可以…
暂无图片
编程学习 ·

工业元宇宙的定义与实施路线图

工业元宇宙的定义与实施路线图 李正海 1 工业元宇宙 给大家做一个关于工业元宇宙的定义。对于工业&#xff0c;从设计的角度来讲&#xff0c;现在的设计人员已经做到了普遍的三维设计&#xff0c;但是进入元宇宙时代&#xff0c;就不仅仅只是三维设计了&#xff0c;我们的目…
暂无图片
编程学习 ·

【leectode 2022.1.15】完成一半题目

有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目&#xff0c;整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题&#xff0c;请返回被选的 N 道题目至少包含多少种知识点类型。 示例 1&#xff1a…
暂无图片
编程学习 ·

js 面试题总结

一、js原型与原型链 1. prototype 每个函数都有一个prototype属性&#xff0c;被称为显示原型 2._ _proto_ _ 每个实例对象都会有_ _proto_ _属性,其被称为隐式原型 每一个实例对象的隐式原型_ _proto_ _属性指向自身构造函数的显式原型prototype 3. constructor 每个prot…
暂无图片
编程学习 ·

java练习代码

打印自定义行数的空心菱形练习代码如下 import java.util.Scanner; public class daYinLengXing{public static void main(String[] args) {System.out.println("请输入行数");Scanner myScanner new Scanner(System.in);int g myScanner.nextInt();int num g%2;//…
暂无图片
编程学习 ·

RocketMQ-什么是死信队列?怎么解决

目录 什么是死信队列 死信队列的特征 死信消息的处理 什么是死信队列 当一条消息初次消费失败&#xff0c;消息队列会自动进行消费重试&#xff1b;达到最大重试次数后&#xff0c;若消费依然失败&#xff0c;则表明消费者在正常情况下无法正确地消费该消息&#xff0c;此时…
暂无图片
编程学习 ·

项目 cg day04

第4章 lua、Canal实现广告缓存 学习目标 Lua介绍 Lua语法 输出、变量定义、数据类型、流程控制(if..)、循环操作、函数、表(数组)、模块OpenResty介绍(理解配置) 封装了Nginx&#xff0c;并且提供了Lua扩展&#xff0c;大大提升了Nginx对并发处理的能&#xff0c;10K-1000K Lu…
暂无图片
编程学习 ·

输出三角形

#include <stdio.h> int main() { int i,j; for(i0;i<5;i) { for(j0;j<i;j) { printf("*"); } printf("\n"); } }
暂无图片
编程学习 ·

stm32的BOOTLOADER学习1

序言 最近计划学习stm32的BOOTLOADER学习,把学习过程记录下来 因为现在网上STM32C8T6还是比较贵的,根据我的需求flash空间小一些也可以,所以我决定使用stm32c6t6.这个芯片的空间是32kb的。 #熟悉芯片内部的空间地址 1、flash ROM&#xff1a; 大小32KB&#xff0c;范围&#xf…
暂无图片
编程学习 ·

通过awk和shell来限制IP多次访问之学不会你打死我

学不会你打死我 今天我们用shell脚本&#xff0c;awk工具来分析日志来判断是否存在扫描器来进行破解网站密码——限制访问次数过多的IP地址&#xff0c;通过Iptables来进行限制。代码在末尾 首先我们要先查看日志的格式&#xff0c;分析出我们需要筛选的内容&#xff0c;日志…
暂无图片
编程学习 ·

Python - 如何像程序员一样思考

在为计算机编写程序之前&#xff0c;您必须学会如何像程序员一样思考。学习像程序员一样思考对任何学生都很有价值。以下步骤可帮助任何人学习编码并了解计算机科学的价值——即使他们不打算成为计算机科学家。 顾名思义&#xff0c;Python经常被想要学习编程的人用作第一语言…
暂无图片
编程学习 ·

蓝桥杯python-数字三角形

问题描述 虽然我前后用了三种做法&#xff0c;但是我发现只有“优化思路_1”可以通过蓝桥杯官网中的测评&#xff0c;但是如果用c/c的话&#xff0c;每个都通得过&#xff0c;足以可见python的效率之低&#xff08;但耐不住人家好用啊&#xff08;哭笑&#xff09;&#xff09…