Posted on 2006-09-08 23:25
oyjpart 阅读(769)
评论(3) 编辑 收藏 引用
//
说实话 我还是挺喜欢HEAP这个数据结构的 写个类的HEAP吧 呵呵
//
by Optimistic
//
本程序是大根堆的操作集合 以及堆排序 优先级队列的堆实现
#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
;
}