java⼤根堆_堆排序算法及其Java实现（以⼤根堆为例）(⼆叉)堆数据结构是⼀种数组对象，如图所⽰(下标从0开始)，它完全可以被视为⼀棵完全⼆叉树。
接下来要出现的⼏个词语，这⾥介绍⼀下:
length[A]: 数组A中元素的个数
heap-size[A]: 存放在数组A中堆的元素的个数，是要排序的元素的个数，在进⾏堆排序时，这个是会变的(减1)
A[0]是树的根，A[i]是数组中的第i个元素(从0开始计数)
PARENT(i): 第i个元素⽗结点的位置，值为 (i - 1)/2
LEFT(i): 第i个元素左孩⼦的位置，值为2i + 1
RIGHT(i): 第i个元素右孩⼦的位置，值为 2i + 2
static int parent(int i) {
return (i - 1)/2;
}
static int left(int i) { //左孩⼦
return 2*i + 1;
}
static int right(int i) { //右孩⼦
return 2*i + 2;
}
操作:
MAX-HEAPIFY: 保持⼤根堆性质，运⾏时间O(lg n)
BUILD-MAX-HEAP: ⼤根堆初始建堆，即在⽆序的输⼊基础上建堆，运⾏时间O(n)
HEAPSORT: 堆排序，对⼀个数组进⾏原地排序，运⾏时间O(n*lg n)
⼀、MAX-HEAPIFY(保持⼤根堆性质)
⼤根堆的性质：A[PARENT(i)] >= A[i]，MAX-HEAPIFY是对⼤根堆进⾏操作的重要⼦程序，后⾯要经常⽤到。
输⼊：以a[i]为根结点的⼦树，且以a的左孩⼦和a的右孩⼦为根节点的⼦树都满⾜⼤根堆性质
输出：树形没有变，但结点顺序可能发⽣改变的⼦树(该树的所有⼦树的根节点的值都⼤于它左右孩⼦的值，保持了⼤根堆性质) static void maxHeapfy(int []a,int i,int heapSize) { //数组a，第i个结点，heapSize是数组中实际要排序的元素的长度
int left = left(i); //有的时候能够递归到叶⼦结点，叶⼦结点⽆后继，下⾯两个if都注意到了这⼀点
int right = right(i);
int largest = i;
二叉树的基本性质
if(left < heapSize && a[left] > a[largest]) { //
largest = left;
}
if(right < heapSize && a[right] > a[largest])
{
largest = right;
}
if(largest != i) { //把最⼤值给⽗结点
a[largest] = a[largest] ^ a[i];
a[i] = a[largest] ^ a[i];
a[largest] = a[largest] ^ a[i];
maxHeapfy(a,largest,heapSize); //发⽣交换之后还要保证⼤根堆性质
}
}
⼆、BUILD-MAX-HEAP(初始建堆)
输⼊：⽆序的⼀组数
输出：⼀组数，按层序对应⼀棵完全⼆叉树，并且在它的每个⼦树中，根节点的值都⼤于其后代结点的值
步骤：⾃底向上，从最后⼀个⾮叶⼦结点开始调⽤MAX-HEAPFY操作，以下图为例
代码实现:
static void buildMaxHeap(int []a,int heapSize) {
for(int i = (heapSize-1)/2;i >= 0;i--) {
maxHeapfy(a,i,heapSize);
}
}
三、堆排序(HEAPSORT)
通过初始建堆，数组中最⼤的元素在A[0]，此时我们把A[0]与A[n-1]互换，对新数组A[0]~A[n-2]重新建堆，然后第⼆⼤的元素⼜落在了A[0]的位置上，此时我们把A[0]与A[n-2]互换…..以此类推，堆的⼤⼩由n-1⼀直降到2，我们得到原输⼊序列的升序排列
代码：
static void heapSort(int []a) {
for(int i = a.length-1;i > 0;i--) {
buildMaxHeap(a,i+1); //堆的⼤⼩从n到2
a[i] = a[0] ^ a[i]; //交换
a[0] = a[0] ^ a[i];
a[i] = a[0] ^ a[i];
}
}
在初始建堆之后，原根结点的左右⼦树均满⾜最⼤堆的性质，所以实际上在对A[0]~A[n-2]进⾏初始建堆的时候，只有在根结点A[0]处执⾏了MAX-HEAPIFY操作，下⾯的代码换⼀种更直观的写法：
static void heapSort(int []a) {
int len = a.length;
buildMaxHeap(a,len); //初始建堆
a[len-1] = a[0] ^ a[len-1]; //交换
a[0] = a[0] ^ a[a.length-1];
a[len-1] = a[0] ^ a[len-1];
for(int i = 1;i
maxHeapfy(a,0,len-i);
a[len-1-i] = a[0] ^ a[len-1-i]; //交换
a[0] = a[0] ^ a[len-1-i];
a[len-1-i] = a[0] ^ a[len-1-i];
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。