Posted on 2006-09-08 23:25
oyjpart 閱讀(776)
評論(3) 編輯 收藏 引用
?
//
說實話?我還是挺喜歡HEAP這個數據結構的?寫個類的HEAP吧?呵呵
//
by?Optimistic
//
本程序是大根堆的操作集合?以及堆排序?優(yōu)先級隊列的堆實現
#include?
<
string
.h
>
#include?
<
iostream
>
using
?
namespace
?std;
template?
<
typename?T
>
class
?MaxHeap????????????????
//
大根堆?(本程序使用下標與結點名相同的格式)
{
public
:
?MaxHeap(
int
?MaxHeapSize?
=
?
10
);
?
~
MaxHeap()
{delete?[]?heap;}
?
int
?Size()
{
return
?heapSize;}
?MaxHeap
<
T
>&
?Insert(
const
?T
&
?x);
?MaxHeap
<
T
>&
?Delete(T
&
?x);
?
void
?MakeHeap(T?
*
?a,?
int
?size,?
int
?ArraySize);
?T?Max()
?
{
??
if
(heapsize?
>
?
0
)?????
//
判溢出
??
return
?heap[
1
];
?}
private
:
?T
*
?heap;
?
int
?heapSize;
?
int
?MaxSize;?
}
;
template?
<
typename?T
>
MaxHeap
<
T
>
::MaxHeap(
int
?MaxHeapSize)?????????
{
?MaxSize?
=
?MaxHeapSize;
?heap?
=
?
new
?T[MaxSize
+
1
];
?heapSize?
=
?
0
;
}
template?
<
typename?T
>
MaxHeap
<
T
>&
?MaxHeap
<
T
>
::Insert(
const
?T
&
?x)?
//
堆的插入?由葉結點向上找位置?在sort中是不需要插入的
{
?
if
(heapSize?
<
?MaxSize)????
?
{
??heapSize
++
;
??
int
?i?
=
?heapSize,?ic?
=
?i
/
2
;
??
while
(ic?
>=
?
1
)
??
{
???
if
(x?
<=
?heap[ic])?
break
;
???heap[i]?
=
?heap[ic];
???i?
=
?ic;
???ic?
=
?i?
/
?
2
;
??}
??heap[i]?
=
?x;
?}
?
return
?
*
this
;
}
template?
<
typename?T
>
MaxHeap
<
T
>&
?MaxHeap
<
T
>
::Delete(T
&
?x)???????
//
堆的刪除?即根結點的刪除?從上到下
{
?
//
在操作上相當與對最后一個結點從上到下的插入
?
if
(heapSize?
>
?
0
)
?
{
??x?
=
?heap[
1
];
??T?y?
=
?heap[heapSize
--
];
??
int
?i?
=
?
1
,?ic?
=
?
2
;??????????????
//
i記錄當前查詢結點?ic記錄其子結點
??
while
(ic?
<=
?heapSize)???????????????
??
{
???
if
(ic
+
1
?
<=
?heapSize?
&&
?heap[ic]?
<
?heap[ic
+
1
])?ic
++
;
???
if
(y?
>=
?heap[ic])?
break
;
???heap[i]?
=
?heap[ic];
???i?
=
?ic;
???ic?
=
?
2
*
i;
??}
??heap[i]?
=
?y;
?}
?
return
?
*
this
;
}
template?
<
typename?T
>
void
?MaxHeap
<
T
>
::MakeHeap(T?
*
?a,?
int
?size,?
int
?ArraySize)?
//
建堆：把數組堆化并處理成大根堆
{
?
//
堆化
?delete?[]?heap;
?heap?
=
?
new
?T[size
+
1
];
?memcpy(heap,?a,?(size
+
1
)
*
sizeof
(T));??????
//
此處不要忘記乘sizeof(T)
?heapSize?
=
?size;
?MaxSize?
=
?ArraySize;
?
//
處理堆
?
int
?i?
=
?heapSize
/
2
;
?
for
(;?i?
>=
?
1
;?i
--
)????????????????????
//
從小到上依次調整
?
{
??T?y?
=
?heap[i];
??
int
?ic?
=
?
2
*
i;
??
while
(ic?
<=
?heapSize)?
??
{
???
if
(ic
+
1
?
<=
?heapSize?
&&
?heap[ic
+
1
]?
>
?heap[ic])?ic
++
;
???
if
(y?
>=
?heap[ic])?
break
;
???heap[ic
/
2
]?
=
?heap[ic];
???ic?
=
?
2
*
ic;
??}
??heap[ic
/
2
]?
=
?y;
?}
}
template?
<
typename?T
>
void
?HeapSort(T?
*
?a,?
int
?n)
{
?MaxHeap
<
T
>
?H(
0
);
?H.MakeHeap(a,?n,?n);
?T?x;
?
for
(
int
?i?
=
?n;?i?
>=
?
1
;?i
--
)
?
{
??H.Delete(x);
??a[i]?
=
?x;
?}
}
int
?main()
{
//
?freopen("heap.in",?"r",?stdin);
?
int
?size,?i,?
*
?a;
?printf(
"
Please?input?the?size?of?array:\n
"
);
?scanf(
"
%d
"
,?
&
size);
?a?
=
?
new
?
int
[size
+
1
];
?printf(
"
Please?input?the?array?to?be?sorted:\n
"
);
?
for
(i
=
1
;?i
<=
size;?i
++
)
??scanf(
"
%d
"
,?
&
a[i]);
?HeapSort(a,?size);
?
for
(i
=
1
;?i
<=
size;?i
++
)
??printf(
"
%4d
"
,?a[i]);
?printf(
"
\n
"
);
?system(
"
Pause
"
);
?
return
?
0
;
}