iis服务器助手广告广告
返回顶部
首页 > 资讯 > 精选 >java利用Heap堆实现PriorityQueue优先队列
  • 514
分享到

java利用Heap堆实现PriorityQueue优先队列

2023-06-03 08:06:23 514人浏览 薄情痞子
摘要

本篇内容介绍了“java利用Heap堆实现PriorityQueue优先队列”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!首先做一个优先队列

本篇内容介绍了“java利用Heap堆实现PriorityQueue优先队列”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

首先做一个优先队列的接口:

import java.util.List;
public interface PriorityQueue {
 void add(Object o);
 void addAll(List elements);
 Object remove(); 
 boolean isEmpty();
 int size();
}

接下来,用java写一个heap结构,实现priority queue接口:

heap是一种二叉树,所遵守的唯一规律为:所有的子节点都要大于(小于)父节点。

增加一个节点,直接加在最后,然后用upheap排序

删除一个节点,则把要删除的节点与跟节点交换,然后删除交换后的根节点(既最后一个点),然后用downheap重新排序

heap的add方法很简单,关键是addall,根据是空heap或非空,,应有不同的算法以保证效率,空heap用bottom-up排序应该是最快的,至于非空的heap,则比较有挑战性,以下是我自己写的一段程序,仅供参考:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Arrays;

public class Heap implements PriorityQueue {

        protected Comparator comparator;

        final static int ROOT_INDEX = 0;
        final static int PRE_ROOT_INDEX = ROOT_INDEX - 1;

        List heap;

        public Heap() {
                heap = new ArrayList();
        }

        public Heap(Comparator c) {
                heap = new ArrayList();
                comparator = c;
        }

       
        public void add(Object o) {
                heap.add(o);

                int index = heap.size() - 1;
                while (index > ROOT_INDEX) {
                        index = stepUpHeap(index);
                }
        }

       
        protected int stepUpHeap(int index) {
                int parentIndex = parent(index);
                Object element = heap.get(index);
                Object parent  = heap.get(parentIndex);
                if (compare(parent, element) > 0) {     // heap is out of order here
                        heap.set(parentIndex, element);
                        heap.set(index, parent);
                        return parentIndex;           // jump to parent of index
                } else                                  // heap is OK
                        return ROOT_INDEX;              // so jump to root
        }

       
        protected int compare(Object element, Object other) {
                if (comparator == null) {
                        Comparable e = (Comparable) element;
                        Comparable o = (Comparable) other;
                        return e.compareTo(o);
                } else
                        return comparator.compare(element, other);
        }

       
        protected int parent(int index) {
                return (index - PRE_ROOT_INDEX) / 2 + PRE_ROOT_INDEX;
        }

        public String toString() {
                return heap.toString();
        }

       
        public boolean isEmpty() {
                return heap.isEmpty();
        }

       
        public int size() {
                return heap.size();
        }

       
        public Object remove() throws RuntimeException{
                if (isEmpty())
                        throw new RuntimeException();

                int index = heap.size() - 1;
                Object least;
                if(index==0){
                        least = heap.get(index);
                        heap.remove(index);
                }
                else{
                        Object element = heap.get(index);
                        least  = heap.get(ROOT_INDEX);
                        heap.set(ROOT_INDEX, element);
                        heap.set(index, least);
                        heap.remove(index);
                        stepDownHeap(ROOT_INDEX);
                }
                return least;
        }

       
        public void addAll(List elements) {
                int numbers = elements.size();
                for(int i=0;i<numbers;i++)
                        heap.add(elements.get(i));

                int n=1,rows=0;
                for(rows=0;n<= heap.size();rows++){
                        n = n*2;
                        }
                for(int i=rows-1;i>=1;i--){
                        for(int j=(int)(Math.pow(2,i-1)-1);j<=(int)(Math.pow(2,i)-2);j++){
                                stepDownHeap(j);
                        }
                }

        }

        public static void sort(Comparable[] data) {
                Heap cpr = new Heap();
                List middle = Arrays.asList(data);
                cpr.addAll(middle);
                for(int i=data.length-1;i>=0;i--)
                        data[i] = (Comparable)(cpr.remove());
        }

        public static void sort(Object[] data, Comparator c) {
                Heap cpr = new Heap(c);
                List middle = Arrays.asList(data);
                cpr.addAll(middle);
                for(int i=data.length-1;i>=0;i--)
                        data[i] = cpr.remove();
        }

        public void stepDownHeap(int index){
                int p = index;
                int c = 2*p + 1;
                Object temp = heap.get(p);
                while(c<heap.size()){
                        if(c+1<heap.size() && compare(heap.get(c+1),heap.get(c))<0)
                                c = c + 1;
                        if(compare(temp,heap.get(c))<=0)
                                break;
                        else {
                                heap.set(p,heap.get(c));
                                p = c;
                                c = 2*p + 1;
                                }
                }
                heap.set(p,temp);
        }
}

最后是一段测试程序:

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class PQtest {
 
 ///////////////////////////////////////////////////////
 //
 // static declarations
 //
 ///////////////////////////////////////////////////////
 
 public static void main(String[] args) {
  PQTest test = new PQTest();
  test.constructor();
  test.add();
  test.remove();
  test.addAll();
  test.sort();
 }

 static int nextIndex;
 final static long SEED = 88888L;
 final static Random random = new Random(SEED);

 static Integer[] arrayData;  // backing store for data
 static List data;

 static void makeData(int n) {
  random.setSeed(SEED);
  arrayData = new Integer[n];
  for (int i = 0; i < n; ++i) {
   arrayData[i] = (new Integer(i));
  }
  data = Arrays.asList(arrayData);
  Collections.shuffle(data, random);
 }
 
 static void testAssert(boolean b, String s) {
  if (!b) throw new RuntimeException(s);
 }
 
 static Comparator comparableComparator() {
  return new Comparator() {
   public int compare(Object x, Object y) {
    return ((Comparable) x).compareTo(y);
   }
  };
 }
 
 static Comparator reverseComparator(Comparator c) {
  return new ReverseComparator(c);
 }
 
 static class ReverseComparator implements Comparator {
  Comparator c;
  ReverseComparator(Comparator c) {
   this.c = c;
  }
  public int compare(Object x, Object y) {
   return - c.compare(x,y);
  }
 }
 
 static CountComparator countComparator(Comparator c) {
  return new CountComparator(c);
 }

 static class CountComparator implements Comparator {
  Comparator c;
  CountComparator(Comparator c) {
   this.c = c;
  }
  int count = 0;
  public int getCount() {
   return count;
  }
  public void clearCount() {
   count = 0;
  }
  public int compare(Object x, Object y) {
   ++count;
   return c.compare(x,y);
  }
 }
 
 ///////////////////////////////////////////////////////
 //
 // instance specific declarations
 //
 ///////////////////////////////////////////////////////
  
 // instance variable
 
 PriorityQueue pq; // priority queue to be tested
 Comparator c;

 // instance methods for testing priority queue operation
 
 void constructor() {
  System.out.println("new Heap()");
  pq = new Heap();
  checkPQ(true, 0);
  System.out.println();
 }

 void add() {
  makeData(16);
  for (int i = 0; i < 16; ++i) {
   Object o = data.get(i);
   System.out.println("add(" + o + ") ...");
   pq.add(o);
   checkPQ(false, i+1);
  }
  System.out.println();
 }
 
 void remove() {
  for (int i = pq.size(); i > 0; --i) {
   checkPQ(false, i);
   System.out.print("remove() = ");
   Object o = pq.remove();
   System.out.println(o);
  }
  checkPQ(true, 0);
  System.out.println();
 }

 void addAll() {
  c = countComparator(comparableComparator());
  pq = new Heap(c);
  makeData(99);
  addN(0,16);
  addN(16,16);
  addN(16,17);
  addN(17,19);
  addN(19,27);
  addN(27,43);
  addN(43,48);
  addN(48,99);
  System.out.println();
 }

 void addN(int from, int to) {
  int size = pq.size();
  List dataN = data.subList(from,to);
  int n = to - from;
  System.out.println("addAll(" + dataN + ") ... " + n + " items ...");
  pq.addAll(dataN);
  checkPQ(false, size+n);
  System.out.println("Comparison count = " + ((CountComparator) c).getCount());
  ((CountComparator) c).clearCount();
 }

 void sort() {
  Comparator c = null;
  
  System.out.println("Testing sort() with natural ordering");  
  sortWithComparator(c);
  System.out.println();

  System.out.println("Testing sort() with reverse natural ordering"); 
  c = reverseComparator(comparableComparator());
  sortWithComparator(c);
  System.out.println();

  System.out.println("Testing sort() with natural ordering and comparison count");  
  c = countComparator(comparableComparator());
  sortWithComparator(c);
  System.out.println("Comparison count = " + ((CountComparator) c).getCount());
  System.out.println();

  System.out.println("Testing sort() with reverse natural ordering and comparison count");  
  c = countComparator(reverseComparator(comparableComparator()));
  sortWithComparator(c);
  System.out.println("Comparison count = " + ((CountComparator) c).getCount());
  System.out.println();  
 }

 void sortWithComparator(Comparator c) {
  makeData(64);
  System.out.println("Unsorted: " + data);
  Heap.sort(arrayData, c);
  System.out.println("Sorted:   " + data);
  System.out.println();
 }

 // helper methods

 void checkPQ(boolean isEmpty, int size) {
  System.out.println("PriorityQueue: " + pq);
  testAssert(pq.isEmpty() == isEmpty,  "isEmpty()");
  testAssert(pq.size() == size,  "size()");
 }
}

对于非空的heap,应该有更快的算法(但是效率都是o(nlogn)),只是结果可能会有所不同,但是仍然是按照heap的排序规则排列。

[@more@]

“java利用Heap堆实现PriorityQueue优先队列”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站,小编将为大家输出更多高质量的实用文章!

--结束END--

本文标题: java利用Heap堆实现PriorityQueue优先队列

本文链接: https://www.lsjlt.com/news/233765.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • java利用Heap堆实现PriorityQueue优先队列
    本篇内容介绍了“java利用Heap堆实现PriorityQueue优先队列”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!首先做一个优先队列...
    99+
    2023-06-03
  • 【Java】PriorityQueue--优先级队列
    目录  一、优先级队列  (1)概念 二、优先级队列的模拟实现 (1)堆的概念  (2)堆的存储方式   (3)堆的创建 堆向下调整 (4)堆的插入与删除 堆的插入  堆的删除 三、常用接口介绍 1、PriorityQueue的特性 2...
    99+
    2023-08-31
    数据结构 java idea 算法 面试
  • Python中的优先队列(priority queue)和堆(heap)
    目录队列和优先队列(Priority Queue)堆(heap)简介初始化构建堆堆的插入(节点上浮)堆的删除(节点下浮)堆的应用队列和优先队列(Priority Queue) 队列是...
    99+
    2024-04-02
  • Java的优先队列PriorityQueue详解
    Java中的优先队列是一种基于优先级的队列,元素按照优先级的顺序进行排序,具有较高优先级的元素在队列的头部,较低优先级的元素在队列的...
    99+
    2023-09-06
    Java
  • Java优先级队列-堆
    Java优先级队列-堆 💐1. 二叉树的顺序存储💐🎃 1.1 存储方式🎃👻1.2 下标关系👻 ...
    99+
    2023-09-04
    java 算法 数据结构
  • java数据结构-堆实现优先队列
    目录一、二叉树的顺序存储1.堆的存储方式 2.下标关系 二、堆(heap)1.概念 2.大/小 根堆2.1小根堆2.2大根堆3.建堆操作 3.1向下调整 4.入队操作 4...
    99+
    2024-04-02
  • C#中实现PriorityQueue优先级队列的代码
    前言 前段时间看到有大佬对.net 6.0新出的PriorityQueue(优先级队列)数据结构做了解析,但是没有源码分析,所以本着探究源码的心态,看了看并分享出来。它不像普通队列先...
    99+
    2024-04-02
  • java 堆(优先级队列)详解
    JAVA堆以及优先级队列详解 一、堆的模拟实现1.1堆的概念1.2 堆的性质1.3堆的存储结构1.4堆的创建1.4.1 只有根节点不满足堆的特性1.4.2 不只有根节点不满足堆的特性1.4.2...
    99+
    2023-10-21
    java 数据结构 优先级对列 heap PriorityQueue 堆排序
  • C#实现优先队列和堆排序
    目录优先队列1.API2.初级实现3.堆的定义二叉堆表示法4.堆的算法上浮(由下至上的堆的有序化)下沉(由上至下的堆的有序化)改进堆排序1.堆的构造2.下沉排序先下沉后上浮优先队列 ...
    99+
    2024-04-02
  • Java数据结构之堆(优先队列)的实现
    堆(优先队列)是一种典型的数据结构,其形状是一棵完全二叉树,一般用于求解topk问题。根据双亲节点大于等于孩子节点或双亲节点小于等于孩子节点,可分为大顶堆和小顶堆,本文实现大顶堆。 ...
    99+
    2024-04-02
  • Java集合框架之PriorityQueue优先级队列实例分析
    这篇文章主要讲解了“Java集合框架之PriorityQueue优先级队列实例分析”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Java集合框架之PriorityQueue优先级队列实例分析...
    99+
    2023-07-02
  • Java数据结构之优先级队列(PriorityQueue)用法详解
    目录概念PriorityQueue的使用小试牛刀(最小k个数) 堆的介绍优先级队列的模拟实现Top-k问题概念 优先级队列是一种先进先出(FIFO)的数据结构,与队列不同的...
    99+
    2024-04-02
  • Java基于堆结构实现优先队列功能示例
    本文实例讲述了Java基于堆结构实现优先队列功能。分享给大家供大家参考,具体如下:package Demo;import java.util.NoSuchElementException;public class JPriorityQueu...
    99+
    2023-05-30
    java 优先队列 ava
  • python 堆和优先队列的使用
    python里面的堆是通过在列表中维护堆的性质实现的。这一点与C++中heap一系列的算法类似,底层是通过堆vector的维护获取堆的性质。 python堆的部分API,其他API查阅文档python_heap_API和 h...
    99+
    2023-01-31
    队列 python
  • Java堆&优先级队列示例讲解(下)
    目录1.优先级队列1.1 概念1.2 内部原理1.3 操作-入队列1.4 操作-出队列(优先级最高)1.5 借用堆实现优先级队列1.6 测试1.优先级队列 1.1 概念 在很多应用中...
    99+
    2024-04-02
  • Java堆&优先级队列示例讲解(上)
    目录1. 二叉树的顺序存储1.1 存储方式1.2 下标关系2. 堆(heap)2.1 概念2.2 操作-(下沉&上浮)本例是最大堆2.3 建堆-完整代码(最大堆)3. 优先级...
    99+
    2024-04-02
  • java编程实现优先队列的二叉堆代码分享
    这里主要介绍的是优先队列的二叉堆Java实现,代码如下:package practice;import edu.princeton.cs.algs4.StdRandom;public class TestMain { public sta...
    99+
    2023-05-30
    java 算法 二叉堆
  • Java数据结构之堆(优先队列)详解
    目录堆的性质堆的分类堆的向下调整堆的建立堆得向上调整堆的常用操作入队列出队列获取队首元素TopK 问题例子数组排序堆的性质 堆逻辑上是一棵完全二叉树,堆物理上是保存在数组中 。 总...
    99+
    2024-04-02
  • Python中的堆和优先队列是如何实现的?
    Python中的堆和优先队列是如何实现的?堆和优先队列是在计算机科学中常用的数据结构。在Python中,我们可以使用heapq模块来实现堆和优先队列。堆是一种特殊的完全二叉树,在堆中,每个父节点的值都比它的子节点的值要小(或大),这样的堆被...
    99+
    2023-10-22
    实现 优先队列
  • JavaScript实现优先级队列
    目录一、优先级队列介绍二、优先级队列封装一、优先级队列介绍 我们知道,普通的队列插入一个元素,数据会被放在后端,并且需要前面所有的元素都处理完成后才会处理前面的数据。但是优先级队列,...
    99+
    2024-04-02
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作