数据结构——堆

简介: 数据结构——堆

堆的特性∶

1.它是完全二叉树,除了树的最后一层结点不需要是满的,其它的每一层从左到右都是满的,如果最后一层结点不是满的,那么要求左满右不满。

2.它通常用数组来实现。

具体方法就是将二叉树的结点按照层级顺序放入数组中,根结点在位置1,它的子结点在位置2和3,而子结点的子结点则分别在位置4,5,6和7,以此类推。


如果一个结点的位置为k,则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样,在不

使用指针的情况下,我们也可以通过计算数组的索引在树中上下移动︰从ak]向上一层,就令k等于k/2,向下一层就令k等于2k或2k+1。

3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点,但这两个子结点的顺序并没有做规定,跟我们之前学习的二叉查找树是有区别的。

image.png

(1)如果 往堆中新插入元素,只需要不断的比较新结点a[k]和它的父结点a[k/2]的大小,然后根据结果完成数据元素的交换 ,就可以完成堆的有序调整。(如果父节点的值比当前结点的值小,则交换位置 )

(2)如果 往堆中删除最大元素 ,第一个元素就是最大元素,删除掉后。将最后一个元素放到索引1处,然后不断的拿 当前节点a[k]和它的子节点a[2k]和a[2k+1]中较大者交换位置 。

//堆代码
public class Heap<T extends Comparable<T>>{
    //存储堆中的元素
    private T[] items;
    //记录堆中元素的个数
    private int N;
    public Heap(int capacity){
        this.items = (T[]) new Comparable[capacity+1]; //因为数组下标0没有使用
        this.N = 0;
    }
    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j){
        return items[i].compareTo(items[j])<0;
    }
    // 交换堆中i索引和j索引处的值
    private void exch(int i, int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
    // 往堆中插入一个元素
    public void insert(T t){
        //因为一开始N=0,这样第一个插入的元素就在items[1],
        items[++N]=t;
        //需要调整元素位置,让堆有序(每个结点都大于其两个子结点)
        swim(N);
    }
    // 使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
    // 不断和父节点比较
    private void swim(int k){
        //如果父节点的值比当前结点的值小,则交换位置
        while(k>1){
            if(less(k/2,k)){
                exch(k/2,k);
            }else{
                break;
            }
            k = k/2;
        }
    }
    // 删除堆中最大的元素,并返回这个最大元素
    public T delMax(){
        //删除最大元素,其实就是删除根结点
        T max = items[1];
        //交换到索引结尾处
        exch(1, N);
        items[N]=null;
        N--;
        sink(1);
        return max;
    }
    // 使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
    // 当前节点a[k]和它的子节点a[2k]和a[2k+1]中较大者交换位置
    private void sink(int k){
        //如果当前已经是最低层了,则不用循环
        while(2*k<=N){
            int max; //暂存较大的子节点
            //<=N 说明存在叶子节点
            if (2*k+1<=N){
                if(less(2*k,2*k+1)){
                    max = 2*k + 1;
                }else{
                    max = 2*k;
                }
            }else{//不存在右子结点
                max = 2*k;
            }
            if(!less(k,max)){
                break;
            }
            exch(k,max);
            //变化k的值
            k = max; //下一次循环
        }
    }
}

下面是堆排序:

十大排序算法——堆排序_龍弟-idea的博客-CSDN博客

相关文章
|
1月前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
39 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
85 16
|
2月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
100 1
|
3月前
|
存储 Java
【数据结构】优先级队列(堆)从实现到应用详解
本文介绍了优先级队列的概念及其底层数据结构——堆。优先级队列根据元素的优先级而非插入顺序进行出队操作。JDK1.8中的`PriorityQueue`使用堆实现,堆分为大根堆和小根堆。大根堆中每个节点的值都不小于其子节点的值,小根堆则相反。文章详细讲解了如何通过数组模拟实现堆,并提供了创建、插入、删除以及获取堆顶元素的具体步骤。此外,还介绍了堆排序及解决Top K问题的应用,并展示了Java中`PriorityQueue`的基本用法和注意事项。
69 5
【数据结构】优先级队列(堆)从实现到应用详解
|
2月前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)
|
2月前
|
存储 算法 分布式数据库
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
【初阶数据结构】理解堆的特性与应用:深入探索完全二叉树的独特魅力
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
2月前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
37 0
|
2月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
2月前
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
49 0