《算法导论(第三版)》第六章，堆排序的应用之最大优先队列

Zedd

《算法导论(第三版)》第六章，堆排序的应用之最大优先队列
. k: J5 w  S7 Q
, @6 b0 `( ^1 X主函数：

• %测试任意功能前，需将其它功能注释了
• 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将会在第一位，
  

$ ?' j7 \& u8 v% r- E2 K, f8 T
5 ~( q+ L7 I, O2 A* dHEAP_INCREASE_KEY

• 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
  9 K; u1 \5 T3 I/ S# o

( N% N; h* a+ i4 O5 T: X( C, H$ F
HEAP_EXTRACT_MAX

• 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
  3 ^$ v0 c, w! G) |+ t- i# _

0 m7 ]+ G; e6 P% e* JMAX_HEAP_INSERT
( y! t4 M! j: ?

• function [A] = MAX_HEAP_INSERT(A,key)%加入新值
• A(end+1)=-inf;%长度+1
• A=HEAP_INCREASE_KEY(A,length(A),key);
• end
  / }/ ~% L/ f* B! q' A- h

; |0 n- n* F2 F: j; f& k$ O6 A
+ U, P, n6 v$ n, D* Z, L( [! \& BMAX_HEAPIFY
* j* p9 Y. i" ^. ?: i  I$ N

• 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
  

* O" S! A9 j1 ]6 f; m: M/ b
9 `, C" u& c  o0 G! k
$ p) U/ ^0 _* s5 d

wu68aq

堆排序的应用之最大优先队列。

wu68aq

堆排序的应用之最大优先队列) 。

gaoxings

堆排序的应用之最大优先队列。