欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

(JAVA) 数据结构 "堆 "简介 - 实现与理论 - 1. 堆

最编程 2024-10-09 14:03:18
...

1.1 堆的定义

堆是计算机科学中一类特殊的数据结构的统称,堆通常可以被看做是一棵完全二叉树的数组对象

1.1.1 堆的特性

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

在这里插入图片描述

  1. 它通常用数组来实现
    • 具体方法就是将二叉树的节点按照层级顺序放入数组汇总,根节点在位置1,它的子节点在位置2和3,而子节点的子节点则分别在位置4,5,6和7,以此类推

在这里插入图片描述

​ 如果一个节点的位置为k,则它的父节点的位置为k/2,而它的两个子节点的位置则分别是2k2k+1

  • 这样在不使用指针的情况下,我们也可以通过计算数组的索引在树中上下移动:
    • a[k]向上一层,就让k等于k/2
    • 向下一层就让k等于2k2k+1
  1. 每个节点都大于等于它的两个子节点。
    • 这里要注意堆中仅仅规定了每个节点大于等于它的两个子节点,但这两个子节点的顺序并没有做规定,跟二叉查找树是有区别的。

1.2 堆的API设计

类名 Heap<T extends Comparable>
构造方法 Heap(int capacity):创建容量为caparity的Heap对象
成员方法 1. private boolean less(int i,int j):判断堆中索引i处的元素是否小于索引j处的元素
2. private void exch(int i,int j):交换堆中i索引和j索引处的值
3. public T delMax():删除堆中最大的元素,并返回这个最大元素
4. public void insert(T t):往堆中插入一个元素
5. private void swim(int k):使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
6. private void sink(int k):使用下沉算法,使索引k处的元素能子啊堆中处于一个正确的位置
成员变量 1. private T[] items:用来存储元素的数组
2. private int N:记录堆中元素的个数

1.3 堆的实现

1.3.1insert插入方法的实现

​ 堆是使用数组完成数据元素的存储的,由于数组的底层是一串连续的内存地址,所以我们要往堆中插入数据,我们只能往数组中从索引0处开始,以此往后存放数据,但是堆汇总堆元素的顺序是有要求的,每一个节点的数据要大于等于它的两个子节点的数据,所以每次插入一个元素都会使得堆中的数据顺序变乱,这个时候我们就需要通过一些方法让刚才插入的这个数据放入到合适的位置。

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

如果往堆中新插入元素,我们只需要不断的比较新节点a[k]和它的父节点a[k/2]的大小,如何根据完成数据元素的交换,就可以完成堆的有序调整

1.3.2 delMax删除最大元素方法的实现

​ 由堆的特性可知,所以1处的元素,也就是根节点就是最大的元素,当我们把根节点的元素删除后,需要由一个新的根节点出现,这时我们可以暂时把队中最后一个元素放到所以1处,充当根节点,但是它右可能不满足堆的有序性需求,这个时候我们就需要通过一些方法,让这个新的根节点放入到合适的位置。
在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

推荐阅读