EDA365电子论坛网
标题:
《算法导论(第三版)》第六章，堆排序的应用之最大优先队列
[打印本页]
作者:
Zedd
时间:
2020-3-10 10:25
标题:
《算法导论(第三版)》第六章，堆排序的应用之最大优先队列
《算法导论(第三版)》第六章，堆排序的应用之最大优先队列
5 y3 d3 F; R" D( O" O
/ |2 S; e/ @, g* I! w# W# m
主函数：
% {6 Q/ i* d9 X* O! N
%测试任意功能前，需将其它功能注释了
clear;clc
A=[16 14 10 8 7 9 3 2 4 1]%测试队列
%[A MAX]=HEAP_EXTRACT_MAX(A) %提取最大值
%HEAP_INCREASE_KEY(A,9,3);%3<4，当前测试会报错
%HEAP_INCREASE_KEY(A,9,15)%15>4，8取代4，并且15会到第二位置
A=MAX_HEAP_INSERT(A,17)%队列长度+1，17将会在第一位，
; P" G \1 @4 T+ N
) L) f+ R" V& @9 J9 c% o
5 M- u# `+ U( c9 ^5 q6 r6 P4 S
HEAP_INCREASE_KEY
9 ?9 a! Z7 y% I7 {
function [A] = HEAP_INCREASE_KEY(A,i,key)
if key<A(i)%新更新的值比原值小，则直接报错
error('new key is smaller than current key');
end
A(i)=key;%更新值
while i>1 & A(floor(i/2))<A(i)%父值比子值小，则一直更新
temp=A(i);
A(i)=A(floor(i/2));
A(floor(i/2))=temp;
i=floor(i/2);
end
end
( j$ L% R. T' L9 K& i3 ?+ X7 ^# X
& s8 F1 X! J+ r* [1 I" [& G0 z
/ K$ x: S2 D- s1 y, _) H2 p( T
HEAP_EXTRACT_MAX
3 S) Y d! H! K, t
function [A,MAX] = HEAP_EXTRACT_MAX(A)
if length(A)<1%A为空，则报错
error('heap underflow!')
end
MAX=A(1);%A(1)就是优先队列的最大值
A(1)=A(end);%末尾的提到最前
A(end)=[];%去掉末尾
A=MAX_HEAPIFY(A,1);%重新进行一次排列
end
: [ b- [) z: j( B; A r. q5 @
, c t# n$ X, V
9 L0 D8 i( z, ?" U
MAX_HEAP_INSERT
6 S( A) {! n! w% q' _: }! {& s9 a2 Y+ B
function [A] = MAX_HEAP_INSERT(A,key)%加入新值
A(end+1)=-inf;%长度+1
A=HEAP_INCREASE_KEY(A,length(A),key);
end
, Y0 u7 a/ f# }6 ~* P
4 i0 [- m9 t* |
( ^6 _6 i0 E3 ?6 P5 [' Y4 B7 V5 q
MAX_HEAPIFY
1 @9 u. a' q& s3 j5 S; O
function [A] = MAX_HEAPIFY(A,i)%前面已经写过了，直接调用
l=2*i;%左节点序号
r=2*i+1;%右节点序号
%比较该节点与左右子节点的大小
if l<=length(A) & A(l)>A(i)
largest=l;
else
largest=i;
end
if r<=length(A) & A(r)>A(largest)
largest=r;
end
%如果最大子节点变换，则交换，继续递归。
if largest~=i
temp=A(i);
A(i)=A(largest);
A(largest)=temp;
A=MAX_HEAPIFY(A,largest);
end
end
x7 i) X. U k* D, H
9 P( P6 j/ G1 u4 v7 x3 y. S" R
* d: u0 ~& H6 l
" K1 M, K! }; i& ^5 U1 V$ D" J
作者:
wu68aq
时间:
2020-3-10 17:48
堆排序的应用之最大优先队列。
作者:
wu68aq
时间:
2020-3-11 16:59
堆排序的应用之最大优先队列) 。
作者:
gaoxings
时间:
2020-3-12 18:15
2 o: y: d1 Z6 S1 X0 G+ ?0 Y
堆排序的应用之最大优先队列。
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2