由於使用陣列來儲存堆積樹，每次將最後一個節點與樹根交換的動作，就是將最小值放至後端的陣列，最後陣列就會變為已排序的狀態。
程式實作. C Java Python
OPENHOME.CC
常見程式演算
|老掉牙
河內塔
費氏數列
巴斯卡三角形
三色旗
老鼠走迷宮
騎士走棋盤
八皇后
八銀幣
康威生命遊戲
字串比對
背包問題
雙色、三色河內塔
得分排行
|「數」
最大訪客數
Eratosthenes篩選求質數
完全數
阿姆斯壯數
大數運算
指定位數的圓周率
|隨機
蒙地卡羅法求PI
洗牌
Craps賭博遊戲
約瑟夫問題
|組構
排列
格雷碼
子集
k組合
因數分解
加法因子
|排序
選擇、插入、氣泡排序
Heap排序-改良的選擇排序
Shell排序-改良的插入排序
Shaker排序-改良的氣泡排序
快速排序（一）
快速排序（二）
合併排序
基數排序
|搜尋
線性搜尋
二分搜尋
插補搜尋
費氏搜尋
|矩陣
稀疏矩陣
多維矩陣降維
上／下三角、對稱矩陣
奇數魔方陣
4N魔方陣
2(2N+1)魔方陣
|運算
中序式轉後序式
後序式運算
Quine
GitHub
Twitter
Facebook
LinkedIn
2DDesigns
3DDesigns
Tags
BuiltwithbyHugo
HOME>
常見程式演算>
排序>
Heap排序-改良的選擇排序
解法思路
程式實作
sort
C
Java
Python
Scala
Ruby
JavaScript
Haskell
Heap排序-改良的選擇排序
December8,2021
選擇排序的概念簡單，以降冪為例，每次從未排序部份選最小值，插入已排序部份的後端，時間主要花費於在整個未排序部份尋找最小值，如果能讓搜尋最小值的方式加快，選擇排序法的速率也就可以加快。
Heap排序會先建立堆積樹（Heaptree），父子節點間的值具有順序關係，可以加快值的搜尋，可算是改良的選擇排序法。
解法思路
堆積樹是個二元樹，父節點最多有兩個子節點，父節點若小於子節點，稱為最小堆積（Minheap），父節點若大於子節點，稱為最大堆積（Maxheap），同一層的節點不考慮大小關係，例如是個最小堆積樹：
若使用陣列來儲存堆積樹的元素，為了計算方便，使用的起始索引是1而不是0，索引1是樹根位置，如果左子節點儲存在陣列中的索引為s，則其父節點的索引為s/2，而右子節點為s+1，就如上圖所示，將上圖的堆積樹轉換為陣列後如下：
若要建立堆積樹，以最小堆積為例，加至堆積樹的元素會先放置在最後一個節點位置，然後檢查父節點是否小於子節點，將小的元素不斷與父節點交換，直到滿足堆積樹的條件為止，例如在上圖的堆積加入一個元素12，則堆積樹的調整方式如下所示：
建立好最小堆積樹後，樹根一定是最小值，將最小值取出，然後調整樹為最小堆積樹，不斷重複這兩個步驟，就可以達到排序的效果。
最小值取出方式是將樹根與最後一個節點交換，然後切下最後一個節點；調整堆積樹的方式，是找出父節點兩子節點中較小的一個進行交換，如下所示：
調整完畢後，樹根節點又是最小值了，於是可以重覆這個步驟，再取出最小值，並調整樹為堆積樹，如下所示：
由於使用陣列來儲存堆積樹，每次將最後一個節點與樹根交換的動作，就是將最小值放至後端的陣列，最後陣列就會變為已排序的狀態。
程式實作
C
Java
Python
Scala
Ruby
JavaScript
Haskell
#include
#include
#defineLEN10
#defineOFFSET1
#defineSWAP(x,y){intt;t=x;x=y;y=t;}
voidheapSort(int*,intlen,int(*)(int,int));
voidheapTree(int*,int,int(*)(int,int));
voidselectFromHeap(int*,int,int(*)(int,int));
voidbubbleLeaf(int*,int,int(*)(int,int));
intisBubbleable(int*,int,int,int(*)(int,int));
voidbubbleRoot(int*,int,int(*)(int,int));
intidxFromChilds(int*,int,int,int(*)(int,int));
intisRightLeafSuitable(int*,int,int,int(*)(int,int));
voidprint(int*,intlen);
intascending(int,int);
intdescending(int,int);
intmain(void){
intnum[LEN]={10,9,1,2,5,3,8,7,12,11};
heapSort(num,LEN,descending);
print(num,LEN);
heapSort(num,LEN,ascending);
print(num,LEN);
system("PAUSE");
return0;
}
voidheapSort(int*num,intlen,int(*compar)(int,int)){
heapTree(num,len,compar);
selectFromHeap(num,len,compar);
}
voidheapTree(int*num,intlen,int(*compar)(int,int)){
inti,end;
for(i=1,end=len+1;iOFFSET;end--){
SWAP(num[1-OFFSET],num[end-OFFSET]);
bubbleRoot(num,end,comp);
}
}
voidbubbleLeaf(int*num,inteleIdx,int(*compar)(int,int)){
intchildIdx,parentIdx;
for(childIdx=eleIdx,parentIdx=eleIdx/2;
isBubbleable(num,childIdx,parentIdx,compar);
childIdx=parentIdx,parentIdx=childIdx/2){
SWAP(num[parentIdx-OFFSET],num[childIdx-OFFSET]);
}
}
intisBubbleable(int*num,intchildIdx,
intparentIdx,int(*compar)(int,int)){
returnchildIdx>OFFSET&&
compar(num[parentIdx-OFFSET],num[childIdx-OFFSET])<0;
}
voidbubbleRoot(int*num,intend,int(*comp)(int,int)){
intparentIdx,childIdx;
for(parentIdx=0+OFFSET,
childIdx=idxFromChilds(num,parentIdx,end,comp);
childIdx0;
parentIdx=childIdx,
childIdx=idxFromChilds(num,parentIdx,end,comp)){
SWAP(num[parentIdx-OFFSET],num[childIdx-OFFSET]);
}
}
intidxFromChilds(int*num,intparentIdx,intend,int(*comp)(int,int)){
intchildIdx=parentIdx*2;
returnisRightLeafSuitable(num,childIdx,end,comp)?
childIdx+1:childIdx;
}
intisRightLeafSuitable(int*num,intchildIdx,
intend,int(*comp)(int,int)){
returnchildIdx0;
}
voidprint(int*arr,intlen){
inti;
for(i=0;i>
intascending(Tt1,Tt2){returnt1.compareTo(t2);}
publicstatic>
intdescending(Tt1,Tt2){return-ascending(t1,t2);}
publicstatic>
voidheapSort(Listlist){heapSort(list,Sort::ascending);}
privatestaticfinalintOFFSET=1;
publicstaticvoidheapSort(
Listlist,Comparatorc){
heapTree(list,c);
selectFromHeap(list,c);
}
privatestaticvoidheapTree(Listlist,Comparatorc){
for(inti=1,end=list.size()+1;ivoidselectFromHeap(Listlist,
Comparatorc){
for(intend=list.size();end>OFFSET;end--){
swap(list,1-OFFSET,end-OFFSET);
bubbleRoot(list,end,c);
}
}
privatestaticvoidbubbleLeaf(Listlist,
inteleIdx,Comparatorc){
for(intchildIdx=eleIdx,parentIdx=eleIdx/2;
isBubbleable(list,childIdx,parentIdx,c);
childIdx=parentIdx,parentIdx=childIdx/2){
swap(list,parentIdx-OFFSET,childIdx-OFFSET);
}
}
privatestaticbooleanisBubbleable(Listlist,intchildIdx,
intparentIdx,Comparatorc){
returnchildIdx>OFFSET&&c.compare(
list.get(parentIdx-OFFSET),list.get(childIdx-OFFSET))<0;
}
privatestaticvoidbubbleRoot(Listlist,
intend,Comparatorc){
for(intparentIdx=0+OFFSET,
childIdx=idxFromChilds(list,parentIdx,end,c);
childIdx0;
parentIdx=childIdx,
childIdx=idxFromChilds(list,parentIdx,end,c)){
swap(list,parentIdx-OFFSET,childIdx-OFFSET);
}
}
privatestaticintidxFromChilds(Listlist,
intparentIdx,intend,Comparatorc){
intchildIdx=parentIdx*2;
returnisRightLeafSuitable(list,childIdx,end,c)?
childIdx+1:childIdx;
}
privatestaticbooleanisRightLeafSuitable(Listlist,
intchildIdx,intend,Comparatorc){
returnchildIdx0;
}
publicstaticvoidmain(String[]args){
Listlist=
newArrayList<>(Arrays.asList(10,9,1,2,5,3,8,7,12,11));
heapSort(list);
out.println(list);
heapSort(list,Sort::descending);
out.println(list);
}
}
defascending(a,b):returna-b
defdescending(a,b):return-ascending(a,b)
__OFFSET=1
defheapSort(xs,comp=ascending):
ifnotxs:
return[]
else:
heapped=heapTree([],xs,comp)
returnselectFromHeap(heapped,[],comp)
defheapTree(heapped,xs,comp):
ifnotxs:
returnheapped
else:
returnheapTree(bubbleLeaf(heapped,xs[0],comp),xs[1:],comp)
defbubbleLeaf(heapped,child,comp):
ifnotheapped:
return[child]
else:
parentIdx=(len(heapped)+1)//2
ifcomp(heapped[parentIdx-__OFFSET],child)<0:
heappedChilds=(heapped[parentIdx-__OFFSET+1:]+
[heapped[parentIdx-__OFFSET]])
heappedParents=heapped[0:parentIdx-__OFFSET]
returnbubbleLeaf(heappedParents,child,comp)+heappedChilds
else:
returnheapped+[child]
defselectFromHeap(heapped,sorted,comp):
iflen(heapped)==1:
returnheapped+sorted
else:
rootSorted=[heapped[0]]+sorted
unheapped=[heapped[-1]]+heapped[1:-1]
leftHeapped=bubbleRoot(unheapped,1,0,comp)
returnselectFromHeap(leftHeapped,rootSorted,comp)
defbubbleRoot(unheapped,parentIdx,heappedLen,comp):
childLIdx=(parentIdx*2)-heappedLen
iflen(unheapped)==1orchildLIdx>len(unheapped):
returnunheapped
else:
childIdx=idxFromChilds(childLIdx,unheapped,comp)
ifcomp(unheapped[childIdx-__OFFSET],unheapped[0])>0:
heapped=([unheapped[childIdx-__OFFSET]]+
unheapped[1:childIdx-__OFFSET])
rightUnheapped=([unheapped[0]]+
unheapped[childIdx+1-__OFFSET:])
returnheapped+bubbleRoot(rightUnheapped,
heappedLen+childIdx,
heappedLen+childIdx-1,comp)
else:
returnunheapped
defidxFromChilds(childLIdx,unheapped,comp):
return(childLIdx+1ifchildLIdx0
elsechildLIdx)
list=[10,9,1,2,5,3,8,7,12,11]
print(heapSort(list))
print(heapSort(list,descending))
objectSort{
privatevalOFFSET=1
defheap[T](xs:List[T],compare:(T,T)=>Boolean):List[T]={
if(xs.isEmpty)Nil
else{
valheapped=heapTree(Nil,xs,compare)
selectFromHeap(heapped,Nil,compare)
}
}
privatedefheapTree[T](heapped:List[T],xs:List[T],
compare:(T,T)=>Boolean):List[T]={
if(xs.isEmpty)heapped
else{
heapTree(bubbleLeaf(heapped,xs(0),compare),xs.tail,compare)
}
}
privatedefbubbleLeaf[T](heapped:List[T],child:T,
compare:(T,T)=>Boolean):List[T]={
if(heapped.isEmpty)List(child)
else{
valparentIdx=(heapped.size+1)/2
if(compare(child,heapped(parentIdx-OFFSET))){
valheappedChilds=
heapped.slice(parentIdx-OFFSET+1,heapped.size)
++List(heapped(parentIdx-OFFSET))
valheappedParents=heapped.slice(0,parentIdx-OFFSET)
bubbleLeaf(heappedParents,child,compare)++heappedChilds
}
elseheapped++List(child)
}
}
privatedefselectFromHeap[T](heapped:List[T],sorted:List[T],
compare:(T,T)=>Boolean):List[T]={
if(heapped.size==1)heapped++sorted
else{
valrootSorted=heapped.head::sorted
valunheapped=heapped.last::
heapped.slice(1,heapped.size-1)
valleftHeapped=bubbleRoot(unheapped,1,0,compare)
selectFromHeap(leftHeapped,rootSorted,compare)
}
}
privatedefbubbleRoot[T](unheapped:List[T],parentIdx:Int,
heappedLen:Int,compare:(T,T)=>Boolean):List[T]={
valchildLIdx=(parentIdx*2)-heappedLen
if(unheapped.size==1||childLIdx>unheapped.size)unheapped
else{
valchildIdx=idxFromChilds(childLIdx,unheapped,compare)
if(compare(unheapped(childIdx-OFFSET),unheapped.head)){
valheapped=unheapped(childIdx-OFFSET)::
unheapped.slice(1,childIdx-OFFSET)
valrightUnheapped=unheapped.head::
unheapped.slice(childIdx+1-OFFSET,unheapped.size)
heapped++bubbleRoot(rightUnheapped,heappedLen+childIdx,
heappedLen+childIdx-1,compare)
}
elseunheapped
}
}
privatedefidxFromChilds[T](childLIdx:Int,
unheapped:List[T],compare:(T,T)=>Boolean)={
if(childLIdx_))
println(Sort.heap[Int](list,_<_ classsort>(a,b){a-b}
@@descending=->(a,b){-@@ascending.call(a,b)}
defself.ascending;@@ascendingend
defself.descending;@@descendingend
OFFSET=1
defself.heap(xs,comp)
ifxs.empty?
[]
else
heapped=heapTree([],xs,comp)
selectFromHeap(heapped,[],comp)
end
end
defself.heapTree(heapped,xs,comp)
ifxs.empty?
heapped
else
heapTree(bubbleLeaf(heapped,xs[0],comp),xs[1..-1],comp)
end
end
private_class_method:heapTree
defself.bubbleLeaf(heapped,child,comp)
ifheapped.empty?
[child]
else
parentIdx=(heapped.size+1)/2
ifcomp.call(heapped[parentIdx-OFFSET],child)<0
heappedChilds=(heapped[parentIdx-OFFSET+1..-1]+
[heapped[parentIdx-OFFSET]])
heappedParents=heapped[0...parentIdx-OFFSET]
bubbleLeaf(heappedParents,child,comp)+heappedChilds
else
heapped+[child]
end
end
end
private_class_method:bubbleLeaf
defself.selectFromHeap(heapped,sorted,comp)
ifheapped.size==1
heapped+sorted
else
rootSorted=[heapped[0]]+sorted
unheapped=[heapped.last]+heapped[1...-1]
leftHeapped=bubbleRoot(unheapped,1,0,comp)
selectFromHeap(leftHeapped,rootSorted,comp)
end
end
private_class_method:selectFromHeap
defself.bubbleRoot(unheapped,parentIdx,heappedLen,comp)
childLIdx=(parentIdx*2)-heappedLen
ifunheapped.size==1orchildLIdx>unheapped.size
unheapped
else
childIdx=idxFromChilds(childLIdx,unheapped,comp)
ifcomp.call(unheapped[childIdx-OFFSET],unheapped[0])>0
heapped=([unheapped[childIdx-OFFSET]]+
unheapped[1...childIdx-OFFSET])
rightUnheapped=([unheapped[0]]+
unheapped[childIdx+1-OFFSET..-1])
heapped+bubbleRoot(rightUnheapped,
heappedLen+childIdx,
heappedLen+childIdx-1,comp)
else
unheapped
end
end
end
private_class_method:bubbleRoot
defself.idxFromChilds(childLIdx,unheapped,comp)
(childLIdx0)?
childLIdx+1:childLIdx
end
private_class_method:idxFromChilds
end
list=[10,9,1,2,5,3,8,7,12,11]
print(Sort.heap(list,Sort.ascending).to_s+"\n")
print(Sort.heap(list,Sort.descending).to_s+"\n")
functionascending(a,b){returna-b;}
functiondescending(a,b){return-ascending(a,b);}
varheapSort=function(){
functionswap(list,i,j){
varele=list[i];
list[i]=list[j];
list[j]=ele;
}
varOFFSET=1;
functionsort(list,c){
heapTree(list,c);
selectFromHeap(list,c);
}
functionheapTree(list,c){
for(vari=1,end=list.length+1;iOFFSET;end--){
swap(list,1-OFFSET,end-OFFSET);
bubbleRoot(list,end,c);
}
}
functionbubbleLeaf(list,eleIdx,c){
for(varchildIdx=eleIdx,parentIdx=parseInt(eleIdx/2);
isBubbleable(list,childIdx,parentIdx,c);
childIdx=parentIdx,parentIdx=parseInt(childIdx/2)){
swap(list,parentIdx-OFFSET,childIdx-OFFSET);
}
}
functionisBubbleable(list,childIdx,parentIdx,c){
returnchildIdx>OFFSET&&c(
list[parentIdx-OFFSET],list[childIdx-OFFSET])<0;
}
functionbubbleRoot(list,end,c){
for(varparentIdx=0+OFFSET,
childIdx=idxFromChilds(list,parentIdx,end,c);
childIdx0;
parentIdx=childIdx,
childIdx=idxFromChilds(list,parentIdx,end,c)){
swap(list,parentIdx-OFFSET,childIdx-OFFSET);
}
}
functionidxFromChilds(list,parentIdx,end,c){
varchildIdx=parentIdx*2;
returnisRightLeafSuitable(list,childIdx,end,c)?
childIdx+1:childIdx;
}
functionisRightLeafSuitable(list,childIdx,end,c){
returnchildIdx0;
}
returnsort;
}();
varlist=[10,9,1,2,5,3,8,7,12,11];
heapSort(list,ascending);
print(list);
heapSort(list,descending);
print(list);
ascendingab=a-b
descendingab=-ascendingab
slicefromtoxs=take(to-from)(dropfromxs)
tailFromfromxs=slicefrom(lengthxs)xs
initUntiluntilxs=slice0untilxs
offset=1
heapSortxscomp=
ifxs==[]then[]
else
letheapped=heapTree[]xscomp
inselectFromHeapheapped[]comp
heapTreeheappedxscomp=
ifxs==[]
thenheapped
elseheapTree(bubbleLeafheapped(headxs)comp)(tailxs)comp
bubbleLeafheappedchildcomp=
ifheapped==[]then[child]
else
letparentIdx=(lengthheapped+1)`div`2
in
if(comp(heapped!!(parentIdx-offset))child)<0then
letheappedChilds=
(tailFrom(parentIdx-offset+1)heapped)++
[heapped!!(parentIdx-offset)]
heappedParents=initUntil(parentIdx-offset)heapped
in(bubbleLeafheappedParentschildcomp)++heappedChilds
else
heapped++[child]
selectFromHeapheappedsortedcomp=
if(lengthheapped==1)thenheapped++sorted
else
letrootSorted=(headheapped):sorted
unheapped=(lastheapped):(init$tailheapped)
leftHeapped=bubbleRootunheapped10comp
inselectFromHeapleftHeappedrootSortedcomp
bubbleRootunheappedparentIdxheappedLencomp=
if(lengthunheapped==1)||(childLIdx>lengthunheapped)
thenunheapped
else
letchildIdx=idxFromChildschildLIdxunheappedcomp
in
ifcomp(unheapped!!(childIdx-offset))(headunheapped)>0
then
letheapped=(unheapped!!(childIdx-offset)):
(slice1(childIdx-offset)unheapped)
rightUnheapped=
(headunheapped):
(tailFrom(childIdx+1-offset)unheapped)
inheapped++
(bubbleRootrightUnheapped(heappedLen+childIdx)
(heappedLen+childIdx-1)comp)
elseunheapped
wherechildLIdx=(parentIdx*2)-heappedLen
idxFromChildschildLIdxunheappedcomp=
ifchildLIdx0
thenchildLIdx+1
elsechildLIdx
main=sequence[print$heapSortlistascending,
print$heapSortlistdescending]
wherelist=[10,9,1,2,5,3,8,7,12,11]
