在现实的生活工作中,有许多情况下都要处理有序的元素,但又不要求全部有序,再或者不要求一次就将它们全部排序,这种情况下一种叫“优先队列”的算法就派上了用场。比如说,不要求全排序一个大数据集合的数据,或内存一次装不下整个数据集,但是要求获得最大或最小的M有序的数组。
本节我们会学习基于二叉堆数据结构的优先队列的实现。优先队列最重要的操作就是删除最大元素和插入元素两种操作。数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中,每个元素都要保证大于等于两外2个特定位置的元素。(当一颗二叉的每个节点都大于等于它的两个孩子节点时,被称为堆有序。)
用数组(堆)实现的完全二叉树,结构严格有灵活,能实现对数级别的插入元素和删除最大元素的操作。代码如下:
/**
* 基于数组(堆)实现的完全二叉树的优先队列
* @author jacky
*
*/
public class MaxPriorityQueue<Key extends Comparable<Key>>{
//基于堆的完全二叉树
private Key[] pq;
//将数据存储在pq[1 ... N]中,pq[0]不使用
private int size = 0;
/**
* 默认创建一个大小为Integer.MAX_VALUE的队列
*/
public MaxPriorityQueue(){
pq = (Key[])new Comparable[Integer.MAX_VALUE];
}
public MaxPriorityQueue(int max){
pq = (Key[])new Comparable[max + 1];
}
/**
* 向优先队列中添加元素,将元素添加到数组的pq[++size]
* @param v
*/
public void push(Key v){
pq[++size] = v;
//由下至上的对有序化
swim(size);
}
/**
* 由下至上的对有序化:循环比较pq[size/2]和pq[k],若pq[size/2] < pq[k]则
* 交换数据,知道k = 1
* @param k
*/
private void swim(int k){
int cmp = k/2;
while(k > 1 && less(cmp,k)){
exch(cmp,k);
cmp = k/2;
}
}
/**
* 将最大的元素从优先队列中取出
* @return
*/
public Key delMax(){
Key max = pq[1];//从根节点得到最大的元素
exch(1,size--);//将其和最后一个节点交换
pq[size+1] = null;//防止越界
sink(1);//由上到下恢复对的有序性
return max;
}
/**
* 由上到下的对有序化
* @param k
*/
private void sink(int k){
while(2 * k <= size){
int j = 2 * k;
if(j < size && less(j,j+1)){
j++;
}else if(!less(k,j)){
break;
}
exch(k,j);
k = j;
}
}
private boolean less(int i,int j){
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i,int j){
Key tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
}
分享到:
相关推荐
优先队列在Java编程中是一种特殊的数据结构,它遵循特定的出队顺序,通常是最小元素(最小优先队列)或最大元素(最大优先队列)先出队。这种数据结构在解决各种问题时非常有用,例如任务调度、事件驱动编程、搜索...
优先队列是一种特殊的数据结构,它允许我们按照优先级顺序处理元素。在计算机科学中,尤其是在算法和数据结构领域,优先队列常用于解决需要快速访问最高优先级元素的问题,如Dijkstra算法或Prim算法。在C语言中,...
"priority_queue_1.0_excitingfbh_matlab优先队列_matlab优先队列_优先队列_"这个标题表明这是一个MATLAB环境下的优先队列实现,可能由excitingfbh开发者创建,版本为1.0。 描述中提到的"pq_create"是创建优先队列...
优先队列是一种特殊的队列,它的主要特性是队首元素具有最高的优先级。在Java中,我们可以使用数组来实现优先队列。这篇文章将探讨如何利用数组实现优先队列,并通过提供的`PriorityQ.java`文件来深入理解其实现原理...
优先队列是一种特殊的数据结构,它允许我们按照优先级顺序处理元素。在计算机科学中,尤其是在算法设计中,优先队列常被用于解决各种问题,如任务调度、事件驱动模拟和图形学等。本实现是用Java编程语言完成的,Java...
优先队列(Priority Queue)是数据结构中的一种特殊队列,它的主要特点是元素的出队顺序不是按照“先进先出”(FIFO)的原则,而是根据每个元素的优先级来决定。这种数据结构广泛应用于各种算法和系统设计中,如事件...
根据给定文件的信息,我们可以详细地探讨一下最大优先队列和最小优先队列的基本操作。 ### 一、优先队列概述 优先队列是一种抽象数据类型,它支持一系列基本操作,如插入、删除等,并且队列中的元素具有不同的...
在讨论采用优先队列式分枝限界法求解0/1背包问题之前,我们需要先了解0/1背包问题的基本概念。0/1背包问题是一种组合优化问题,它的目标是在不超过背包总承重的前提下,从给定的一组物品中选择物品,使得选取物品的...
优先队列是一种特殊的数据结构,它允许我们根据元素的优先级进行操作,通常用于处理具有紧急程度的任务。在这个实验报告中,优先队列是通过最大堆实现的,最大堆是一种完全二叉树,其中每个父节点的优先权重都大于或...
优先队列是一种特殊的队列,其中元素按照优先级顺序进行排列。在计算机科学中,它是一种数据结构,常用于处理需要快速访问最高优先级元素的问题。在这个话题中,我们将深入探讨与“简单的优先队列”相关的几个核心...
### 利用堆实现的优先队列 #### 引言 在计算机科学领域,优先队列是一种非常重要的数据结构,它被广泛应用于多种算法中,如任务调度、事件驱动模拟等场景。相比于传统队列,优先队列允许插入元素时指定一个优先级...
优先队列是一种特殊的数据结构,它允许我们按照优先级处理元素。在计算机科学中,特别是在算法和数据结构领域,优先队列通常用于实现任务调度、事件驱动模拟、图的最短路径计算等场景。在C语言中,由于没有内置的...
优先队列是一种特殊类型的队列,它遵循“优先”原则,即队列中的元素可以根据某种优先级被处理。在数据结构课程设计中,优先队列数据类型(priority_queue)是核心概念之一,常用于实现高效的调度、搜索和优化问题。...
"STL优先队列、队列、栈" STL(Standard Template Library)中的优先队列、队列、栈是三个非常重要的数据结构,它们在实际应用中有着广泛的应用。本文将详细介绍STL中的优先队列、队列、栈,包括它们的定义、操作、...
### 基于K叉树的优先队列 #### 概述 本文介绍了一种新的优先队列实现方法,即**基于K叉树的优先队列**。此方法旨在优化传统二叉堆基础上的优先队列算法,提高处理大规模数据集时的效率。通过构建一种特殊的K叉树堆...
优先队列、图等总结及习题 优先队列是一种特殊的队列结构,它的出队顺序是根据元素的优先权决定的,而不是元素入队的顺序。优先队列的操作包括查找、插入和删除,删除操作是根据优先权高或低的次序进行的。 一、...
在IT领域,多级优先队列(Multi-Level Priority Queues)是一种重要的数据结构,尤其在操作系统设计中扮演着核心角色。这种数据结构允许我们高效地处理具有不同优先级的任务,通常用于调度算法,如进程调度或任务...
优先队列是一种特殊的数据结构,它允许我们快速访问或删除具有最高优先级的元素。在计算机科学中,优先队列通常用作调度任务、事件驱动模拟等场景的基础。本程序通过堆来实现优先队列,堆是一种二叉树形结构,满足堆...
### 关于STL中优先队列的用法 #### 一、引言 在C++标准模板库(STL)中,优先队列是一种非常有用的容器类型,它提供了高效的访问最大或最小元素的方式,通常用于解决需要频繁进行查找、插入和删除最大(或最小)值...
本项目通过C++语言实现了批处理作业调度问题的解决方案,利用了优先队列式分支限界法和回溯法这两种高级算法。 1. **批处理作业调度问题**:批处理作业调度是指将一组离散的作业分配给计算机系统,以最大限度地提高...