在堆排序基础上顺便实现下优先队列,纯粹为实现下优先队列的思想,也顾不上代码丑陋了,嘿嘿,自己学习。
public class PriorityQueue<T extends Comparable<T>> {
/**
* 和对排序中一样,第零个元素不做用
*/
private T[] queue;
private int heapSize;
/**
* 初始化队列
* @param a
*/
@SuppressWarnings("unchecked")
public void initPriorityQueue(T[] a){
HeapSortor.buildMaxHeap(a);
heapSize = a.length - 1;
queue = (T[]) Array.newInstance(Comparable.class, 100);
for(int i = 1; i < a.length; ++i)
queue[i] = a[i];
a = null;
}
/**
* 获取优先多列中第一个元素
* @return
*/
public T maxItem(){
return queue[1];
}
/**
* 从队列中删除并返回最大元素,同时通过HeapSortor.maxHeapify保持优先队列特性
* @return
*/
public T extractMax(){
T max = queue[1];
HeapSortor.swap(queue,1, heapSize);
heapSize--;
HeapSortor.maxHeapify(queue, 1, heapSize);
return max;
}
/**
* 将队列的第i个元素增加到key,然后调整使得队列保持优先队列特性
* @param key
* @param i
*/
public void increaseKey(T key, int i){
if( key.compareTo(queue[i]) < 0 )
throw new RuntimeException("The key is not greater than queue[i]");
queue[i] = key;
int parent = i/2;
while( parent > 0 && queue[parent].compareTo(queue[i]) < 0){
HeapSortor.swap(queue, i, parent);
i = parent;
}
}
/**
* 插入关键字key到优先多列中
* @param key
*/
public void insert(T key){
queue[++heapSize] = key;
increaseKey(key, heapSize);
}
}
分享到:
相关推荐
优先队列在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. **批处理作业调度问题**:批处理作业调度是指将一组离散的作业分配给计算机系统,以最大限度地提高...