📄 heap sort.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0050)http://linux.wku.edu/~lamonml/algor/sort/heap.html -->
<HTML><HEAD><TITLE>Heap Sort</TITLE>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META content="Michael Lamont" name=Author>
<META
content="Description, source code, algorithm analysis, and empirical results for heap sort."
name=Description>
<STYLE type=text/css>.BlueLink {
COLOR: #0000ff; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 10pt; TEXT-DECORATION: none
}
A.BlueLink:hover {
COLOR: #0000ff; TEXT-DECORATION: underline
}
.TitleText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 24pt; TEXT-DECORATION: none
}
.HeadText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 18pt; TEXT-DECORATION: none
}
.BodyText {
COLOR: #000000; FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 10pt; TEXT-DECORATION: none
}
.SectionText {
FONT-FAMILY: verdana,arial,helvetica; FONT-SIZE: 14pt
}
.ComText {
FONT-FAMILY: courier,fixed; FONT-SIZE: 10pt
}
</STYLE>
<META content="MSHTML 5.00.3700.6699" name=GENERATOR></HEAD>
<BODY><A class=BlueLink href="http://linux.wku.edu/~lamonml/kb.html">Knowledge
Base</A> > <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/">Algorithms & Data Structures</A>
> <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/index.html">Sorting
Algorithms</A>
<P><B class=TitleText>Heap Sort</B>
<HR align=left noShade SIZE=1 width="40%">
<P></P>
<P class=BodyText><FONT class=SectionText><B>Algorithm Analysis</B></FONT><BR>
<P class=BodyText>The heap sort is the slowest of the <I>O</I>(<I>n</I> log
</I>n</I>) sorting algorithms, but unlike the <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/merge.html">merge</A> and <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/quick.html">quick</A> sorts it
doesn't require massive recursion or multiple arrays to work. This makes it the
most attractive option for <I>very</I> large data sets of millions of items.
<P class=BodyText>The heap sort works as it name suggests - it begins by
building a heap out of the data set, and then removing the largest item and
placing it at the end of the sorted array. After removing the largest item, it
reconstructs the heap and removes the largest remaining item and places it in
the next open position from the end of the sorted array. This is repeated until
there are no items left in the heap and the sorted array is full. Elementary
implementations require two arrays - one to hold the heap and the other to hold
the sorted elements.
<P class=BodyText>To do an in-place sort and save the space the second array
would require, the algorithm below "cheats" by using the same array to store
both the heap and the sorted array. Whenever an item is removed from the heap,
it frees up a space at the end of the array that the removed item can be placed
in.
<P class=BodyText><B>Pros:</B> In-place and non-recursive, making it a good
choice for extremely large data sets.<BR><B>Cons:</B> Slower than the <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/merge.html">merge</A> and <A
class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/quick.html">quick</A> sorts.
<P class=BodyText><FONT class=SectionText><B>Empirical Analysis</B></FONT><BR>
<CENTER><I class=BodyText>Heap Sort Efficiency</I><BR><IMG
alt="Heap Sort Efficiency Graph" src="Heap Sort_files/heap.jpg"> </CENTER>
<P class=BodyText>As mentioned above, the heap sort is slower than the merge and
quick sorts but doesn't use multiple arrays or massive recursion like they do.
This makes it a good choice for really large sets, but most modern computers
have enough memory and processing power to handle the faster sorts unless over a
million items are being sorted.
<P class=BodyText>The "million item rule" is just a rule of thumb for common
applications - high-end servers and workstations can probably safely handle
sorting tens of millions of items with the quick or merge sorts. But if you're
working on a common user-level application, there's always going to be some
yahoo who tries to run it on junk machine older than the programmer who wrote
it, so better safe than sorry.
<P class=BodyText><FONT class=SectionText><B>Source Code</B></FONT><BR>Below is
the basic heap sort algorithm. The <FONT class=ComText>siftDown()
</FONT>function builds and reconstructs the heap.
<P>
<CENTER>
<TABLE bgColor=#eeeeee border=0 cellSpacing=10 class=ComText width="90%">
<TBODY>
<TR>
<TD><FONT class=ComText><PRE><B>void</B> heapSort(<B>int</B> numbers[], <B>int</B> array_size)
{
<B>int</B> i, temp;
<B>for</B> (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);
<B>for</B> (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}
<B>void</B> siftDown(<B>int</B> numbers[], <B>int</B> root, <B>int</B> bottom)
{
<B>int</B> done, maxChild, temp;
done = 0;
<B>while</B> ((root*2 <= bottom) && (!done))
{
<B>if</B> (root*2 == bottom)
maxChild = root * 2;
<B>else if</B> (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
<B>else</B>
maxChild = root * 2 + 1;
<B>if</B> (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
<B>else</B>
done = 1;
}
}
</PRE></FONT></TD></TR></TBODY></TABLE></CENTER>
<P class=BodyText>A sample C program that demonstrates the use of the heap sort
may be <A class=BlueLink
href="http://linux.wku.edu/~lamonml/algor/sort/heap.c">downloaded here</A>. </P>
<HR align=center noShade SIZE=1 width="100%">
<A class=BlueLink href="http://linux.wku.edu/~lamonml/">Michael's
Homepage</A> <A class=BlueLink
href="http://linux.wku.edu/">WKU-Linux</A> </BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -