深入了解Java数据结构和算法之堆

目录
  • 1、堆的定义
  • 2、遍历和查找
  • 3、移除
  • 4、插入
  • 5、完整的Java堆代码
  • 总结

1、堆的定义

①、它是完全二叉树,除了树的最后一层节点不需要是满的,其它的每一层从左到右都是满的。注意下面两种情况,第二种最后一层从左到右中间有断隔,那么也是不完全二叉树。

②、它通常用数组来实现。  

这种用数组实现的二叉树,假设节点的索引值为index,那么:

节点的左子节点是 2*index+1,

节点的右子节点是 2*index+2,

节点的父节点是 (index-1)/2。

③、堆中的每一个节点的关键字都大于(或等于)这个节点的子节点的关键字。

这里要注意堆和前面说的二叉搜索树的区别,二叉搜索树中所有节点的左子节点关键字都小于右子节点关键字,在二叉搜索树中通过一个简单的算法就可以按序遍历节点。但是在堆中,按序遍历节点是很困难的,如上图所示,堆只有沿着从根节点到叶子节点的每一条路径是降序排列的,指定节点的左边节点或者右边节点,以及上层节点或者下层节点由于不在同一条路径上,他们的关键字可能比指定节点大或者小。所以相对于二叉搜索树,堆是弱序的。

2、遍历和查找

前面我们说了,堆是弱序的,所以想要遍历堆是很困难的,基本上,堆是不支持遍历的。

对于查找,由于堆的特性,在查找的过程中,没有足够的信息来决定选择通过节点的两个子节点中的哪一个来选择走向下一层,所以也很难在堆中查找到某个关键字。

因此,堆这种组织似乎非常接近无序,不过,对于快速的移除最大(或最小)节点,也就是根节点,以及能快速插入新的节点,这两个操作就足够了。

3、移除

移除是指删除关键字最大的节点(或最小),也就是根节点。

根节点在数组中的索引总是0,即maxNode = heapArray[0];

移除根节点之后,那树就空了一个根节点,也就是数组有了一个空的数据单元,这个空单元我们必须填上。

第一种方法:将数组所有数据项都向前移动一个单元,这比较费时。

第二种方法:

  • ①、移走根
  • ②、把最后一个节点移动到根的位置
  • ③、一直向下筛选这个节点,直到它在一个大于它的节点之下,小于它的节点之上为止。

具体步骤如下:

图a表示把最后一个节点移到根节点,图b、c、d表示将节点向下筛选到合适的位置,它的合适位置在最底层(有时候可能在中间),图e表示节点在正确位置的情景。

注意:向下筛选的时候,将目标节点和其子节点比较,谁大就和谁交换位置。

4、插入

插入节点也很容易,插入时,选择向上筛选,节点初始时插入到数组最后第一个空着的单元,数组容量大小增一。然后进行向上筛选的算法。

注意:向上筛选和向下不同,向上筛选只用和一个父节点进行比较,比父节点小就停止筛选了。

5、完整的Java堆代码

首先我们要知道用数组表示堆的一些要点。若数组中节点的索引为x,则:

节点的左子节点是 2*index+1,

节点的右子节点是 2*index+2,

节点的父节点是 (index-1)/2。

注意:"/" 这个符号,应用于整数的算式时,它执行整除,且得到是是向下取整的值。

package com.ys.tree.heap;

public class Heap {

    private Node[] heapArray;
    private int maxSize;
    private int currentSize;

    public Heap(int mx) {
        maxSize = mx;
        currentSize = 0;
        heapArray = new Node[maxSize];
    }

    public boolean isEmpty() {
        return (currentSize == 0)? true : false;
    }

    public boolean isFull() {
        return (currentSize == maxSize)? true : false;
    }

    public boolean insert(int key) {
        if(isFull()) {
            return false;
        }
        Node newNode = new Node(key);
        heapArray[currentSize] = newNode;
        trickleUp(currentSize++);
        return true;
    }
    //向上调整
    public void trickleUp(int index) {
        int parent = (index - 1) / 2; //父节点的索引
        Node bottom = heapArray[index]; //将新加的尾节点存在bottom中
        while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
            heapArray[index] = heapArray[parent];
            index = parent;
            parent = (parent - 1) / 2;
        }
        heapArray[index] = bottom;
    }

    public Node remove() {
        Node root = heapArray[0];
        heapArray[0] = heapArray[--currentSize];
        trickleDown(0);
        return root;
    }
    //向下调整
    public void trickleDown(int index) {
        Node top = heapArray[index];
        int largeChildIndex;
        while(index < currentSize/2) { //while node has at least one child
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = leftChildIndex + 1;
            //find larger child
            if(rightChildIndex < currentSize &&  //rightChild exists?
                    heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) {
                largeChildIndex = rightChildIndex;
            }
            else {
                largeChildIndex = leftChildIndex;
            }
            if(top.getKey() >= heapArray[largeChildIndex].getKey()) {
                break;
            }
            heapArray[index] = heapArray[largeChildIndex];
            index = largeChildIndex;
        }
        heapArray[index] = top;
    }
    //根据索引改变堆中某个数据
    public boolean change(int index, int newValue) {
        if(index < 0 || index >= currentSize) {
            return false;
        }
        int oldValue = heapArray[index].getKey();
        heapArray[index].setKey(newValue);
        if(oldValue < newValue) {
            trickleUp(index);
        }
        else {
            trickleDown(index);
        }
        return true;
    }

    public void displayHeap() {
        System.out.println("heapArray(array format): ");
        for(int i = 0; i < currentSize; i++) {
            if(heapArray[i] != null) {
                System.out.print(heapArray[i].getKey() + " ");
            }
            else {
                System.out.print("--");
            }
        }
    }
}
class Node {
    private int iData;
    public Node(int key) {
        iData = key;
    }

    public int getKey() {
        return iData;
    }

    public void setKey(int key) {
        iData = key;
    }
}

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • 带你了解Java数据结构和算法之递归

    目录 1.递归的定义 2.求一个数的阶乘:n! 3.递归的二分查找 4.分治算法 5.汉诺塔问题 6.归并排序 7.消除递归 8.递归的有趣应用 ①.求一个数的乘方 ②.背包问题 ③.组合:选择一支队伍 9.总结 1.递归的定义 递归,就是在运行的过程中调用自己. 递归必须要有三个要素: ①.边界条件 ②.递归前进段 ③.递归返回段 当边界条件不满足时,递归前进:当边界条件满足时,递归返回. 2.求一个数的阶乘:n! 规定: ①.0!=1 ②.1!=1 ③.负数没有阶乘 上面的表达式我们先用fo

  • 带你了解Java数据结构和算法之高级排序

    目录 1.希尔排序 ①.直接插入排序 ②.希尔排序图解 ③.排序间隔选取 ④.knuth间隔序列的希尔排序算法实现 ⑤.间隔为2h的希尔排序 2.快速排序 ①.快速排序的基本思路 ②.快速排序的算法实现 ③.快速排序图示 ④.快速排序完整代码 ⑤.优化分析 总结 1.希尔排序 希尔排序是基于直接插入排序的,它在直接插入排序中增加了一个新特性,大大的提高了插入排序的执行效率.所以在讲解希尔排序之前,我们先回顾一下直接插入排序. ①.直接插入排序 直接插入排序基本思想是每一步将一个待排序的记录,插入

  • 带你了解Java数据结构和算法之哈希表

    目录 1.哈希函数的引入 ①.把数字相加 ②.幂的连乘 2.冲突 3.开放地址法 ①.线性探测 ②.装填因子 ③.二次探测 ④.再哈希法 4.链地址法 5.桶 6.总结 1.哈希函数的引入 大家都用过字典,字典的优点是我们可以通过前面的目录快速定位到所要查找的单词.如果我们想把一本英文字典的每个单词,从 a 到 zyzzyva(这是牛津字典的最后一个单词),都写入计算机内存,以便快速读写,那么哈希表是个不错的选择. 这里我们将范围缩小点,比如想在内存中存储5000个英文单词.我们可能想到每个单词

  • 带你了解Java数据结构和算法之二叉树

    目录 1.树 2.二叉树 3.查找节点 4.插入节点 5.遍历树 6.查找最大值和最小值 7.删除节点 ①.删除没有子节点的节点 ②.删除有一个子节点的节点 ③.删除有两个子节点的节点 ④.删除有必要吗? 8.二叉树的效率 9.用数组表示树 10.完整的BinaryTree代码 11.哈夫曼(Huffman)编码 ①.哈夫曼编码 ②.哈夫曼解码 12.总结 1.树 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点通过连接它们的边组成一个

  • 带你了解Java数据结构和算法之2-3-4树

    目录 1.2-3-4 树介绍 2.搜索2-3-4树 3.插入 1.节点分裂 2.根的分裂 4.完整源码实现 5.2-3-4树和红黑树 ①.对应规则 ②.操作等价 6.2-3-4 树的效率 总结 1.2-3-4 树介绍 2-3-4树每个节点最多有四个字节点和三个数据项,名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数.对于非叶节点有三种可能的情况: ①.有一个数据项的节点总是有两个子节点: ②.有二个数据项的节点总是有三个子节点: ③.有三个数据项的节点总是有四个子节点: 简而言之

  • 带你了解Java数据结构和算法之链表

    目录 1.链表(Linked List) 2.单向链表(Single-Linked List) ①.单向链表的具体实现 ②.用单向链表实现栈 4.双端链表 ①.双端链表的具体实现 ②.用双端链表实现队列 5.抽象数据类型(ADT) 6.有序链表 7.有序链表和无序数组组合排序 8.双向链表 9.总结 前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷.在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会

  • 深入了解Java数据结构和算法之堆

    目录 1.堆的定义 2.遍历和查找 3.移除 4.插入 5.完整的Java堆代码 总结 1.堆的定义 ①.它是完全二叉树,除了树的最后一层节点不需要是满的,其它的每一层从左到右都是满的.注意下面两种情况,第二种最后一层从左到右中间有断隔,那么也是不完全二叉树. ②.它通常用数组来实现. 这种用数组实现的二叉树,假设节点的索引值为index,那么: 节点的左子节点是 2*index+1, 节点的右子节点是 2*index+2, 节点的父节点是 (index-1)/2. ③.堆中的每一个节点的关键字

  • Java 数据结构与算法系列精讲之二叉堆

    目录 概述 优先队列 二叉堆 二叉堆实现 获取索引 添加元素 siftUp 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列 优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆 二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • Java数据结构与算法之栈(动力节点Java学院整理)

    stack,中文翻译为堆栈,其实指的是栈,heap,堆.这里讲的是数据结构的栈,不是内存分配里面的堆和栈. 栈是先进后出的数据的结构,好比你碟子一个一个堆起来,最后放的那个是堆在最上面的. 队列就是排队买苹果,先去的那个可以先买. 栈 public class Stack { private int array[]; private int max; private int top; public Stack(int max){ this.max = max; array = new int[m

  • java数据结构与算法之桶排序实现方法详解

    本文实例讲述了java数据结构与算法之桶排序实现方法.分享给大家供大家参考,具体如下: 基本思想: 假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数.将区间[0, M)划分为n个大小相等的子区间(桶),将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <M辅助数组B[0..n-1]是一指针数组,指向桶(链表).将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. [桶-

  • Java数据结构之优先级队列(堆)图文详解

    目录 一.堆的概念 二.向下调整 1.建初堆 2.建堆 三.优先级队列 1.什么是优先队列? 2.入队列 3.出队列 4.返回队首元素 5.堆的其他TopK问题 总结: 总结 一.堆的概念 堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时: (1)ki >= k2i 且 ki >= k(2i+1) ——大根堆 (2) ki <= k2i 且 ki <= k(2i+1) ——小根堆 简单来说: 堆是具有以下性质的完全二叉树:(1)每个结点的

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • java数据结构与算法之快速排序详解

    本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

  • Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

随机推荐