java编程实现优先队列的二叉堆代码分享

这里主要介绍的是优先队列的二叉堆Java实现，代码如下：

package practice;
import edu.princeton.cs.algs4.StdRandom;
public class TestMain {
  public static void main(String[] args) {
    int[] a = new int[20];
    for (int i = 0; i < a.length; i++) {
      int temp = (int)(StdRandom.random()*100);
      a[i] = temp;
    }
    for (int i : a) {
      System.out.print(i+" ");
    }
    System.out.println();
    PQHeap pq = new PQHeap();
    for (int i = 0; i < 20; i++) {
      pq.insert(a[i]);
    }
    System.out.println();
    for (int i = 0; i < 20; i++) {
      System.out.print(pq.delMax()+" ");
    }
  }
}
/*
 * 优先队列的堆实现
 * 二叉堆，每个元素有两个子元素，两个子元素均比自己小
 */
class PQHeap{
  private int[] a;
  private int p = 1;
  public PQHeap() {
    a = new int[2];
  }
  /*
   * 插入元素
   */
  public void insert(int elements) {
    if (p == a.length) { resize(a.length*2); }
    a[p++] = elements;
    swim(p - 1); //将刚插入的元素上浮到正确位置
  }
  /*
   * 返回并删除最大元素
   */
  public int delMax() {
    if (p == a.length/4) { resize(a.length/2); }
    int result = a[1]; //找出最大元素
    exch(1, --p); //将最后一个元素移到顶端
    a[p] = 0;
    sink(1); //将刚移上去的元素沉下去，使堆有序
    return result;
  }
  public boolean isEmpty() {
    return p == 0;
  }
  public int size() {
    return p;
  }
  public void show() {
    for (int i : a) {
      System.out.print(i+" ");
    }
    System.out.println();
  }
  /*
   * 上浮元素
   */
  private void swim(int k) { //将元素与父元素比较，比父元素大则换位置
    while (k > 1 && a[k/2] < a[k]) {
      exch(k/2, k);
      k = k/2;
    }
  }
  private void sink(int k) { //将元素与子元素比较，比子元素小则和两个中较大的那个换位置
    while (2*k < p && (a[k] < a[2*k + 1]) || (a[k] < a[2*k])) {
      if (a[2*k + 1] > a[2*k]) { exch(k, 2*k + 1); k = 2*k + 1; }
      else           { exch(k, 2*k); k = 2*k; }
    }
  }
  private void resize(int length) {
    int[] b = new int[length]; //将数组长度改变
    for (int i = 0; i < p; i++) { //将数组复制
      b[i] = a[i];
    }
    a = b; //让a指向b的内存空间
  }
  /*
   * 交换
   */
  private void exch (int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}

总结

以上就是本文关于java编程实现优先队列的二叉堆代码分享的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：java集合中list的用法代码示例、Java编程接口调用的作用及代码分享、java并发学习之BlockingQueue实现生产者消费者详解等，有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • 详解Java数据结构和算法（有序数组和二分查找）

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • Java实现的最大匹配分词算法详解

    Java实现的最大匹配分词算法详解

    本文实例讲述了Java实现的最大匹配分词算法.分享给大家供大家参考,具体如下: 全文检索有两个重要的过程: 1分词 2倒排索引 我们先看分词算法 目前对中文分词有两个方向,其中一个是利用概率的思想对文章分词. 也就是如果两个字,一起出现的频率很高的话,我们可以假设这两个字是一个词.这里可以用一个公式衡量:M(A,B)=P(AB)/P(A)P(B),其中 A表示一个字,B表示一个字,P(AB)表示AB相邻出现的概率,P(A)表示A在这篇文章中的频度,P(B)表示B在这篇文章中的频度.用概率分词的好

  • Java实现的猴子吃桃问题算法示例

    本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

  • Java常用加密算法实例总结

    本文实例总结了Java常用加密算法.分享给大家供大家参考,具体如下: 项目中第一次深入地了解到加密算法的使用,现第一阶段结束,将使用到的加密算法和大家分享一下: 首先还是先给大家普及一下常用加密算法的基础知识 基本的单向加密算法 BASE64 严格地说,属于编码格式,而非加密算法 MD5(Message Digest algorithm 5,信息摘要算法) SHA(Secure Hash Algorithm,安全散列算法) 复杂的加密算法 RSA(算法的名字以发明者的名字命名:Ron Rives

  • Java实现分解任意输入数的质因数算法示例

    Java实现分解任意输入数的质因数算法示例

    本文实例讲述了Java实现分解任意输入数的质因数算法.分享给大家供大家参考,具体如下: 分解任意输入数的质因数: 质因数概念:任何一个合数都可以写成几个质数相乘的形式.其中每个质数都是这个合数的因数,叫做这个合数的分解质因数.分解质因数只针对合数. 例如:12 = 2x2x3  18 = 2 x 3 x 3等等 下面来讲解一下这个算法的思路:第一:我们首先写一个求素数的函数:第二;我们做一个分解质因数的函数,然后在其中引入素数函数来判断是否为素数: 下面给出代码(仅供参考): package j

  • java编程实现优先队列的二叉堆代码分享

    这里主要介绍的是优先队列的二叉堆Java实现,代码如下: package practice; import edu.princeton.cs.algs4.StdRandom; public class TestMain { public static void main(String[] args) { int[] a = new int[20]; for (int i = 0; i < a.length; i++) { int temp = (int)(StdRandom.random()*1

  • Java编程用两个栈实现队列代码分享

    题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

  • Python实现二叉堆

    Python实现二叉堆

    优先队列的二叉堆实现 在前面的章节里我们学习了"先进先出"(FIFO)的数据结构:队列(Queue).队列有一种变体叫做"优先队列"(Priority Queue).优先队列的出队(Dequeue)操作和队列一样,都是从队首出队.但在优先队列的内部,元素的次序却是由"优先级"来决定:高优先级的元素排在队首,而低优先级的元素则排在后面.这样,优先队列的入队(Enqueue)操作就比较复杂,需要将元素根据优先级尽量排到队列前面.我们将会发现,对于下一

  • 彻底搞定堆排序:二叉堆

    彻底搞定堆排序:二叉堆

    目录 二叉堆 插入 删除 构建 二叉堆代码实现 总结 二叉堆 什么是二叉堆 二叉堆本质上是一种完全二叉树,它分为两个类型 最大堆:最大堆的任何一个父节点的值,都大于等于它的左.右孩子节点的值(堆顶就是整个堆的最大元素) 最小堆:最小堆的任何一个父节点的值,都小于等于它的左.右孩子节点的值(堆顶就是整个堆的最小元素) 二叉堆的根节点叫做堆顶 二叉堆的基本操作 插入节点 删除节点 构建二叉堆 这几种操作都基于堆的自我调整,所谓堆自我调整,就是把一个不符合堆的完全二叉树,调整成一个堆,下面以最小堆为例

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

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

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

  • Java语言实现二叉堆的打印代码分享

    Java语言实现二叉堆的打印代码分享

    二叉堆是一种特殊的堆,二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树).二叉堆有两种:最大堆和最小堆.最大堆:父结点的键值总是大于或等于任何一个子节点的键值:最小堆:父结点的键值总是小于或等于任何一个子节点的键值. 打印二叉堆:利用层级关系 我这里是先将堆排序,然后在sort里执行了打印堆的方法printAsTree() public class MaxHeap<T extends Comparable<? super T>> { private T[] data; pr

  • Java实现二叉堆、大顶堆和小顶堆

    Java实现二叉堆、大顶堆和小顶堆

    目录 什么是二叉堆 什么是大顶堆.小顶堆 建堆 程序实现 建立大顶堆 逻辑过程 程序实现 建立小顶堆 逻辑过程 程序实现 从堆顶取数据并重构大小顶堆 什么是二叉堆 二叉堆就是完全二叉树,或者是靠近完全二叉树结构的二叉树.在二叉树建树时采取前序建树就是建立的完全二叉树.也就是二叉堆.所以二叉堆的建堆过程理论上讲和前序建树一样. 什么是大顶堆.小顶堆 二叉堆本质上是一棵近完全的二叉树,那么大顶堆和小顶堆必然也是满足这个结构要求的.在此之上,大顶堆要求对于一个节点来说,它的左右节点都比它小:小顶堆要求

  • python下实现二叉堆以及堆排序的示例

    堆是一种特殊的树形结构, 堆中的数据存储满足一定的堆序.堆排序是一种选择排序, 其算法复杂度, 时间复杂度相对于其他的排序算法都有很大的优势. 堆分为大头堆和小头堆, 正如其名, 大头堆的第一个元素是最大的, 每个有子结点的父结点, 其数据值都比其子结点的值要大.小头堆则相反. 我大概讲解下建一个树形堆的算法过程: 找到N/2 位置的数组数据, 从这个位置开始, 找到该节点的左子结点的索引, 先比较这个结点的下的子结点, 找到最大的那个, 将最大的子结点的索引赋值给左子结点, 然后将最大的子结点

  • C语言每日练习之二叉堆

    C语言每日练习之二叉堆

    目录 一.堆的概念 1.概述 2.定义 3.性质 4.作用 二.堆的存储结构 1.根结点编号 2.孩子结点编号 3.父结点编号 4.数据域 5.堆的数据结构 三.堆的常用接口 1.元素比较 2.交换元素 3.空判定 4.满判定 5.上浮操作 6.下沉操作 四.堆的创建 1.算法描述 2.动画演示 3.源码详解 五.堆元素的插入 1.算法描述 2.动画演示 3.源码详解 五.堆元素的删除 1.算法描述 2.动画演示 3.源码详解 总结 一.堆的概念 1.概述 堆是计算机科学中一类特殊的数据结构的统

  • 理解二叉堆数据结构及Swift的堆排序算法实现示例

    理解二叉堆数据结构及Swift的堆排序算法实现示例

    二叉堆的性质 1.二叉堆是一颗完全二叉树,最后一层的叶子从左到右排列,其它的每一层都是满的 2.最小堆父结点小于等于其每一个子结点的键值,最大堆则相反 3.每个结点的左子树或者右子树都是一个二叉堆 下面是一个最小堆: 堆的存储 通常堆是通过一维数组来实现的.在起始数组为 0 的情形中: 1.父节点i的左子节点在位置 (2*i+1); 2.父节点i的右子节点在位置 (2*i+2); 3.子节点i的父节点在位置 floor((i-1)/2); 维持堆的性质 我们以最大堆来介绍(后续会分别给出最大堆和

随机推荐