public class HeapSort
{
int [] a = {3,1,5,2,4,9,8,7,6,4};
//数组的索引以0开始 ID也是从0开始
//父节点的索引
public int parentID(int childID)
{
return (childID-1)/2;
}
//左孩子的索引
public int leftChildID(int parentID)
{
return parentID*2+1;
}
/*
创建大顶堆,将数组初始为一个大顶堆
*/
public void creatMaxHeap()
{
int lastID = a.length-1;
for(int i = parentID(lastID); i >= 0 ; i--)
{
int k=i;
while(leftChildID(k) <= lastID)
{
int j = leftChildID(k);
if(j < lastID) //如果有两个孩子
{
if(a[j] < a[j+1]) //选大的那个孩子
{
j++;
}
}
if(a[k] < a[j]) 如果父结点比孩子小
{
int temp = a[k];
a[k] = a[j];
a[j] = temp;
k=j;
}
else break;
}
}
}
//调整大顶堆
public void maintainHeap(int lastID)
{
int k=0;
while(k <= parentID(lastID))
{
int j = leftChildID(k);
if( j < lastID)
{
if(a[j] <= a[j+1])
j++;
}
if( a[k] <a[j] )
{
int temp = a[j];
a[j] = a[k];
a[k] = temp ;
k = j;
}
else break;
}
}
public void heapSort()
{
creatMaxHeap();
int lastID = a.length-1;
while(lastID > 0)
{
int temp = a[lastID];
a[lastID] = a[0];
a[0] = temp;
lastID--;
if(lastID > 0)
maintainHeap(lastID);
}
}
public void printA()
{
for(int i = 0; i< a.length; i++)
{
System.out.println(a[i]);
}
}
public static void main(String args[])
{
HeapSort hs = new HeapSort();
hs.heapSort();
hs.printA();
}
}
分享到:
相关推荐
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在本场景中,我们关注的是堆排序的源代码,它适用于openSUSE 11.4操作系统,并且是使用GCC version 4.5.1编译器编译的。在这个名为"sort...
本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,父节点的值总是大于或等于其子节点;而在小顶堆中,父节点的值总是小于或等于其子节点。在C++中,我们可以利用STL中的`...
【堆排序算法详解】 堆排序是一种高效的比较排序算法,其主要思想是利用堆这种数据结构进行数据的排序。堆是一个近似完全二叉树的结构,同时满足堆的性质:即父节点的键值总是大于或等于(在最大堆中)或小于或等于...
堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆通常被理解为一个完全二叉树,其中每个父节点的值都大于或等于(大顶堆)或小于或等于(小顶堆)其子节点的值。堆排序算法...
在这个名为“学生成绩管理中实现堆排序”的项目中,我们看到一个C++编写的学生成绩管理系统,它使用了堆排序方法来管理并排序学生的成绩。 首先,让我们详细了解一下堆。堆通常是一个完全二叉树,可以分为最大堆和...