优先队列时间复杂度（在最坏的情况下，下列排序方法中时间复杂度最小的是（）A.冒泡排序 B.快速排序 C.插入排序D.堆排序）

本文目录

• 在最坏的情况下，下列排序方法中时间复杂度最小的是（）A.冒泡排序 B.快速排序 C.插入排序D.堆排序
• 优先队列的实例
• 优先级队列和队列有什么区别
• 简述采用无序链表和有序链表时优先队列入队和出队操作时间复杂度是多少
• 堆排序时间复杂度是什么
• 实现优先队列的初始化，查找，插入，删除操作，并且控制其查找，插入，删除操作的算法时间复杂度为O（logn

在最坏的情况下，下列排序方法中时间复杂度最小的是（）A.冒泡排序 B.快速排序 C.插入排序D.堆排序

答案是D，堆排序。

选项中的四种排序方法的最坏时间复杂度、最好时间复杂度 、平均时间复杂度分别为：

A、冒泡排序： O(n2) 、O(n) 、O(n2)。

B、快速排序： O(n2) 、O(nlog2n)、 O(nlog2n)。

C、插入排序： O(n2)、 O(n) 、O(n2)。

D、堆排序： O(nlog2n)、 O(nlog2n)、 O(nlog2n)。

所以，在最坏情况下，冒泡排序时间复杂度=快速排序时间复杂度=插入排序时间复杂度= O(n2)》堆排序时间复杂度= O(nlog2n)。答案选D。

扩展资料：

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序中堆的操作：

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点。

创建最大堆：将堆中的所有数据重新排序。

堆排序：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

优先队列的实例

有限的元素集合,每个元素都有一个优先权
操作
Create ( ):创建一个空的优先队列
Size ( ):返回队列中的元素数目
Max ( ):返回具有最大优先权的元素
Insert (x):将x插入队列
DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至x
}
优先队列插入和删除元素的复杂度都是O(log2n)，所以很快。
另一种描述方法是采用有序线性表,当元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为( 1 ),插入操作所需时间为(n).
例：
假设我们对机器服务进行收费.每个用户每次使用机器所付费用都是相同的,但每个
用户所需要服务时间都不同.为获得最大利润,假设只要有用户机器就不会空闲,我们可以把
等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需服务时间.当一个新的
用户需要使用机器时,将他/她的请求加入优先队列.一旦机器可用,则为需要最少服务时间
(即具有最高优先权)的用户提供服务.
如果每个用户所需时间相同,但用户愿意支付的费用不同,则可以用支付费用作为优先权,
一旦机器可用,所交费用最多的用户可最先得到服务,这时就要选择最大优先队列.
下面是数组实现的二叉堆，其中MAX_SIZE是数组的最大长度；ElementType是其中元素的类型；Priority(x: ElementType) 是一个函数，返回值是元素x的优先级，当然也可以用一个Priority数组来保存每个元素的优先级(在这个打字员问题中就应该用一个数组来保存每个元素的优先级，在这个问题中优先级就是从初始密码转换到该密码所需的操作的数目)。
type
PriorityQueue = record
contents: array [1..MAX_SIZE]of ElementType;
last : integer;
end;
{ 将一个优先队列变空 }
procedure MakeNull(var A: PriorityQueue);
begin
A.last := 0;
end;
{ 向优先队列A中插入一个元素x }
procedure Insert(x: ElementType; var A: PriorityQueue);
var
i: integer;
temp:ElementType;
begin
if A.last = MAX_SIZE then
Error(’Priority Queue is full.’)
else begin
A.last := A.last + 1;
A.contents[A.last] := x;
i := A.last;
while (i 》 1) and ( Priority(A.contents) 《 Priority(A.contents[i div 2]) do
begin
temp := A.contents;
A.contents:= A.contents[i div 2];
A.contents[i div 2] := temp;
i := i div 2;
end; { end of while }
end; { end of else }
end; { end of Insert }
{ 删除优先队列对头的那个优先级最小的元素，并将其值返回 }
function DeleteMin(var A: PriorityQueue): ElementType;
var
minimun : ElementType;
i : integer;
begin
if A.last = 0 then
Error(’Priority Queue is empty. ’)
else begin
minimun := A.contents;
A.contents := A.contents[A.last];
A.last := A.last - 1;
i := 1;
while i 《 (A.last div 2) do
begin
if (Priority(A.contents[2*i]) 《 Priority(A.contents[2*i+1])) or (2*i = A.last)
then j := 2*i;
else j := 2*i + 1;
{ j节点是i节点具有较高优先级的儿子，当i节点只有一个儿子的时候，j节点是i节点的唯一儿子 }
if Priority(A.contents) 》 Priority(A.contents[j]) then
begin
temp := A.contents;
A.contents:= A.contents[j];
A.contents[j] := temp;
i := j;
end
else begin { 不能再向下推了 }
DeleteMin := minimum;
exit;
end;
end; { end of while }
{ 这时已经到达叶结点 }
DeleteMin := minimum;
exit;
end; { end of else }
end; { end of DeleteMin }
//二叉堆就是优先队列（父节点大于子节点）

优先级队列和队列有什么区别

优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素
　　优先队列的类定义
　　#include 《assert.h》
　　#include 《iostream.h》
　　$include 《stdlib.h》
　　const int maxPQSize = 50; //缺省元素个数
　　template 《class Type》 class PQueue {
　　public:
　　PQueue ( );
　　~PQueue ( ) { delete [ ] pqelements; }
　　void PQInsert ( const Type & item );
　　Type PQRemove ( );
　　void makeEmpty ( ) { count = 0; }
　　int IsEmpty ( ) const
　　{ return count == 0; }
　　int IsFull ( ) const
　　{ return count == maxPQSize; }
　　int Length ( ) const { return count; }
　　private:
　　Type *pqelements; //存放数组
　　int count; //队列元素计数
　　}
　　优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priorityq u e u e)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.
　　最大优先权队列的抽象数据类型描述如ADT 9-1所示,最小优先队列的抽象数据类型描述与之类似,只需将最大改为最小即可.
　　ADT 最大优先队列的抽象数据类型描述抽象数据类型
　　M a x P r i o r i t y Q u e u e{
　　实例 有限的元素集合,每个元素都有一个优先权
　　操作
　　Create ( ):创建一个空的优先队列
　　Size ( ):返回队列中的元素数目
　　Max ( ):返回具有最大优先权的元素
　　I n s e rt (x):将x插入队列
　　DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至x
　　}
　　优先队列插入和删除元素的复杂度都是O(lgn)，所以很快。
　　另一种描述方法是采用有序线性表,当元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为( 1 ),插入操作所需时间为(n).
　　例：
　　假设我们对机器服务进行收费.每个用户每次使用机器所付费用都是相同的,但每个
　　用户所需要服务时间都不同.为获得最大利润,假设只要有用户机器就不会空闲,我们可以把
　　等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需服务时间.当一个新的
　　用户需要使用机器时,将他/她的请求加入优先队列.一旦机器可用,则为需要最少服务时间
　　(即具有最高优先权)的用户提供服务.
　　如果每个用户所需时间相同,但用户愿意支付的费用不同,则可以用支付费用作为优先权,
　　一旦机器可用,所交费用最多的用户可最先得到服务,这时就要选择最大优先队列.

简述采用无序链表和有序链表时优先队列入队和出队操作时间复杂度是多少

采用无序链表的队列，无论是直接在表头还是表尾插入，时间复杂度都是O(1) （链表有尾指针）
但是出队时需要从头到尾找最优先元素，因此时间复杂度为O(n)

如果是有序链表，则插入时找插入点的时间复杂度为O(n)
但是直接出链表表头（也就是队头元素）的时间复杂度为O(1)

堆排序时间复杂度是什么

堆排序时间复杂度，主要在每次选取最大数之后，重新建堆的过程以及初始化堆过程。

堆排序是指利用堆积树这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。

堆是一个优先级队列，对于大顶堆而言，堆顶元素的权值最大。将待排序的数组建堆，然后不断地删除堆顶元素，就实现了排序。

堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

实现优先队列的初始化，查找，插入，删除操作，并且控制其查找，插入，删除操作的算法时间复杂度为O（logn

#include 《stdio.h》
#include 《stdlib.h》

struct MyHeap
{
int* pnData;
int nSize;
}

int IncreaseKey(MyHeap* pHeap, int nPos)
{
//循环和他父节点判断，只要 nPos 》 1他就有父节点
while(nPos 》 1)
{
int nMax = pHeap-》pnData[nPos];
int nParent = nPos / 2;
if (nMax 》 pHeap-》pnData[nParent])
{
pHeap-》pnData[nPos] = pHeap-》pnData[nParent];
pHeap-》pnData[nParent] = nMax;
nPos = nParent;
}
else
{
break;
}
}

return 1;
}

int Insert(MyHeap* pHeap, int nData)
{
++pHeap-》nSize; //添加数据到末尾
pHeap-》pnData[pHeap-》nSize] = nData;
IncreaseKey(pHeap, pHeap-》nSize);
return 1;
}
int PopMaxHeap(MyHeap* pHeap)
{
int nMax = pHeap-》pnData; //得到最大元素
int nPos = 1; //起始位1，因为他弹出，所以是这里开始破坏堆得性质的
int nChild = nPos * 2; //他的左孩子的位置，

//循环填充，用最大孩子填充父节点
while(nChild 《= pHeap-》nSize)
{
int nTemp = pHeap-》pnData[nChild];
if (nChild + 1 《= pHeap-》nSize &&
nTemp 《 pHeap-》pnData[nChild + 1])
{
++nChild;
nTemp = pHeap-》pnData[nChild];
}
pHeap-》pnData[nPos] = nTemp;
nPos = nChild;
nChild *= 2;
}
pHeap-》pnData[nPos] = pHeap-》pnData[pHeap-》nSize];
--pHeap-》nSize;
return nMax;
}
int main()
{
MyHeap myHeap; //定义一个堆
myHeap.pnData = (int*)::malloc(sizeof(int) *11); //申请数据空间
myHeap.nSize = 0; //初始大小为0

for (int i = 1; i 《= 10; ++i) //给优先队列堆里添加数据
{
Insert(&myHeap, i);
}

for (int i = 1; i 《= 10; ++i) //测试优先队列是否建立成功
{
printf(“%d “, myHeap.pnData[i]);
}
printf(“\n“);

while(myHeap.nSize 》 0) //逐一弹出队列的最大值。并验证
{
printf(“%d “, PopMaxHeap(&myHeap));
}
printf(“\n“);

free(myHeap.pnData);
return 0;
}