public class HeapUtil {
/**
* Heap数据结构是由列表或者数组抽象而来
* 这个数据结构可以看作是一个不完整的二叉树
* 规定列表的第一个元素为二叉树的根结点
* 并且假设 parentIndex = i,则leftChildIndex = 2*i,rightChildIndex = 2*i + 1
* 1<=index<=array.legnth + 1
*
* 最大堆的定义是对于array[parentIndex] >= array[leftChildIndex] && array[parentIndex] >= array[rightChildIndex]
* 最小堆则相反
* T(N) = O(logN)
* @param array
* @param index
*/
public static void maxHeapify(int[] array, int index, int startIndex, int endIndex){
int leftChildIndex = (index + 1) * 2;
int rightChildIndex = leftChildIndex + 1;
if(leftChildIndex > endIndex + 1) {
//说明是叶子结点
return ;
}
int turnWhere = 0;
int maxValOfChildren = rightChildIndex > endIndex + 1 ? array[leftChildIndex - 1]
: Math.max(array[leftChildIndex - 1], array[rightChildIndex - 1]);
if(array[index] >= maxValOfChildren){
//没必要交换
return;
}else{
//0:根节点和左边互换
//1:根节点和右边互换
if(rightChildIndex <= endIndex + 1 && maxValOfChildren == array[rightChildIndex - 1]){
turnWhere = 1;
int temp = array[index];
array[index] = array[rightChildIndex - 1];
array[rightChildIndex - 1] = temp;
}else{
int temp = array[index];
array[index] = array[leftChildIndex - 1];
array[leftChildIndex - 1] = temp;
}
}
if(turnWhere == 0){
maxHeapify(array, leftChildIndex - 1, startIndex, endIndex);
}else{
maxHeapify(array, rightChildIndex - 1, startIndex, endIndex);
}
}
/**
* 将一个数组转换成一个最大堆
* T(N) = O(N)
* 这个时间复杂度不能简单的看作O(NlogN)
* 对于长度为N的数组,(我们不考虑不完整二叉树的情况),有N/2个叶子节点
* 对于叶子节点的父节点来说maxHeapify实际上只需要做一次交换即可
* 同理对于叶子节点的父节点的父节点来说maxHeapify实际上只需要做2次交换
* 所以对于一个深度为L的二叉树,做一次maxHeapify实际包含的O(1)操作为L次
* 那么对于N/4(叶子结点总数为N/2则其父节点个数为N/4)个深度为1的父节点运行的时间为N/4 * C(C表示常数时间)
* 对于N/8个深度为2的父节点运行的时间为N/8 * 2 * C
* .
* .
* .
* 对于根结点来说,只有一个并且深度为lgN运行时间为1 * lgN * C
* 则T(N) = N/4 * 1 * C + N/8 * 2 * C + N/16 * 3 * C + ... + 1 * lgN * C
* 为了更好的表示我们假设N/4=2^k
* 则buildMaxHeapFromArray的运行时间可以表示为
* C * 2^k * (1/2^0 + 2/2^1 + 3/2^2 + ... + (k+1)/2^k)
* (1/2^0 + 2/2^1 + 3/2^2 + ... + (k+1)/2^k)是一个有上界的常数
* 则T(N) = C * N/4 = O(N)
*/
public static void buildMaxHeapFromArray(int[] array, int startIndex, int endIndex){
//问题1:为什么从n/2开始
//因为对于任何长度为n的数组A,A[n/2 + 1......n]都是叶子节点
//所以n/2是最后一个非叶子节点,以该节点为根结点的局部二叉树的深度=1
for (int i = (endIndex - startIndex + 1) / 2; i >= startIndex; i--) {
maxHeapify(array, i, startIndex, endIndex);
}
}
/**
* 通过最大堆使得输入的无序数组array排序
* @param array
* @return
*/
public static int[] heapSort(int[] array){
int[] sortedArray = new int[array.length];
for (int i = 0; i < sortedArray.length; i++) {
//step1.构造最大堆
buildMaxHeapFromArray(array, 0, array.length - i - 1);
sortedArray[i] = array[0];
array[0] = array[array.length - i - 1];
}
for (int i = 0; i < array.length; i++) {
System.out.print(sortedArray[i] + ",");
}
return null;
}
public static void main(String args[]) {
heapSort(new int[] {21, 14, 10, 15, 33, 2, 3, 16, 4, 1});
}
}
public class Node {
public Node(int val, Node leftChild, Node rightChild){
this.val = val;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
private int val;
private Node leftChild;
private Node rightChild;
/**
* Getter method for property leftChild.
*
* @return property value of leftChild
*/
public Node getLeftChild() {
return leftChild;
}
/**
* Setter method for property leftChild.
*
* @param leftChild value to be assigned to property leftChild
*/
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
/**
* Getter method for property rightChild.
*
* @return property value of rightChild
*/
public Node getRightChild() {
return rightChild;
}
/**
* Setter method for property rightChild.
*
* @param rightChild value to be assigned to property rightChild
*/
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
/**
* Getter method for property val.
*
* @return property value of val
*/
public int getVal() {
return val;
}
/**
* Setter method for property val.
*
* @param val value to be assigned to property val
*/
public void setVal(int val) {
this.val = val;
}
}
网友评论