IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 从头开始设计一个数据结构—堆 -> 正文阅读

[数据结构与算法]从头开始设计一个数据结构—堆

一、堆的定义

堆树的定义如下:
(1)堆树是一颗完全二叉树;
(2)堆树中某个节点的值总是不大于或不小于其孩子节点的值;
(3)堆树中每个节点的子树都是堆树。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。
当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

二、堆的特性

已知双亲(parent)的下标,则:

  • 左孩子(left)下标 = 2 * parent + 1;
  • 右孩子(right)下标 = 2 * parent + 2;

已知孩子(不区分左右)(child)下标,则:

  • 双亲(parent)下标 = (child - 1) / 2;

三、堆的分类

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆
在这里插入图片描述

四、堆的操作

4.1 堆的建立

  1. 倒序遍历数列,因为下标在size/2 - 1之后的节点都是叶子结点,所以可以从size/2-1位
    置开始倒序遍历,减少比较次数。
  2. 对二叉树中的元素挨个进行沉降处理,沉降过程为:把遍历到的节点与左右子节点中的最小值比对,如果比最小值要大,那么和孩子节点交换数据,反之则不作处理,继续倒序遍历。
  3. 沉降后的节点,再次沉降,直到叶子节点。

4.2 堆的插入

  1. 新元素默认插入末尾
  2. 指定最后一个元素为当前元素,执行上浮操作

4.3 堆的删除

  1. 取根元素
  2. 把最后一个元素赋值为根节点
  3. 指定根节点为起始节点,执行下沉操作

4.4 堆的上浮

  1. 以指定元素为启点
  2. 比较当前节点元素与其父元素大小
  3. 如果当前节点元素小于其父节点元素,则交互2个节点元素的值,把其父节点置为当前节点;否则算法结束。
  4. 重复步骤2~3,直到当前节点为根元素。

4.5 堆的下沉

  1. 以指定元素为启点
  2. 比较当前节点元素与其子节点元素大小,取最小值
  3. 如果当前节点元素为最小元素,则结束算法;如果左子节点为最小元素,则交互2个节点元素的值,把其左子节点节点置为当前节点;如果右子节点为最小元素,则交互2个节点元素的值,把其右子节点节点置为当前节点;
  4. 重新获取当前节点的左右子节点
  5. 重复步骤2~4,直到当前节点的左右子节点都为空。.

五、堆的实现

public class heap {
    private int [] heapArr;
    private int size=0;
    public heap(){
        heapArr=new int[8];
    }
    public heap(int num){
        heapArr=new int[num];
    }
    public heap(int [] arr){
        heapArr=arr;
        build(arr);
    }

    /**
     * 1.从最后一个父节点开始进行沉降即可
     * @param arr
     */
    private void build(int [] arr){
        for(int i=arr.length/2 - 1;i>=0;i--){
            sinkDown(i);
        }
    }

    /**
     * 1.插入到最后的那个元素,如果大小已经和数组一样大,则进行扩容
     * 2.执行元素校验,检查插入元素是否符合堆的特性,不符合则进行调整,插入采用上浮操作
     */

    public void insert(int des){
        if(size>=heapArr.length){
            resize();
        }
        heapArr[size]=des;
        floatUp(size);
        size++;
    }

    /**
     * 1.交换堆底元素与堆顶元素,为了保持堆的完全二叉树结构,从底部交换方便处理一些
     * 2.弹出堆底部元素,从对顶开始下沉
     */
    public int pop(){
        int temp=heapArr[0];
        heapArr[0]=heapArr[size];
        size--;
        //下沉
        sinkDown(0);
        return temp;
    }
    public void resize(){
        heapArr= Arrays.copyOf(heapArr, heapArr.length*2);
    }

    /**
     * 大顶堆,父元素最大
     * 小顶堆,父元素最小
     * 我们以小顶堆为例
     * 1.与父元素比较,双亲(parent)下标 = (child - 1) / 2;
     * 2.交换两者的位置
     * 3.检查父元素是否符合要求
     * @param index
     */
    private void floatUp(int index){

        if(index<0){
            return;
        }
        int parent=(index-1)/2;
        if(heapArr[parent]>heapArr[index]){
           int temp=heapArr[parent];
           heapArr[parent]=heapArr[index];
           heapArr[index]=temp;
           //检查父元素是否符合要求
            floatUp(parent);
        }
    }

    /**
     * 大顶堆,父元素最大
     * 小顶堆,父元素最小
     * 我们以小顶堆为例
     * 左孩子(left)下标 = 2 * parent + 1;
     * 右孩子(right)下标 = 2 * parent + 2
     *
     * 1.检查两个子元素与父元素比较
     *
     * @param parent
     */
    private void sinkDown(int parent){
        if(parent<0){
            return;
        }

        int leftChild=2 * parent + 1;
        int rightChild=2 * parent + 2;

        int minIndex;
        if(heapArr[leftChild]>heapArr[rightChild]){
            minIndex=rightChild;
        }else{
            minIndex=leftChild;
        }
        //父元素大于子元素的话则进行交换
        if(heapArr[parent]>heapArr[minIndex]){
            int temp=heapArr[parent];
            heapArr[parent]=heapArr[minIndex];
            heapArr[minIndex]=temp;
            sinkDown(minIndex);
        }

    }
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-13 12:32:05  更:2021-08-13 12:33:46 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/28 20:53:30-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码