堆排序

package org.ewell.spd;

public class Main {
	public static void main(String[] args) {
		int[] array = new int[] { 90, 1, 2, 3, 4, 33, 23, 7, 8, 45, 9, 10, 14,
				16 };
		MaxHeap maxheap = new MaxHeap(array);
		System.out.println("执行最大堆化前堆的结构：");
		printHeapTree(maxheap.heap);
		maxheap.BuildMaxHeap();
		System.out.println("执行最大堆化后堆的结构：");
		printHeapTree(maxheap.heap);
		maxheap.HeapSort();
		System.out.println("执行堆排序后数组的内容");
		printHeap(maxheap.heap);

	}

	private static void printHeapTree(int[] array) {
		for (int i = 1; i < array.length; i = i * 2) {
			for (int k = i - 1; k < 2 * (i) - 1 && k < array.length; k++) {
				System.out.print(array[k] + " ");
			}
			System.out.println();
		}
	}

	private static void printHeap(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
	}

}

 

package org.ewell.spd;

public class MaxHeap {
	public int[] heap;
	public int heapsize;

	public MaxHeap(int[] array) {
		this.heap = array;
		this.heapsize = heap.length;
	}

	public void BuildMaxHeap() {
		for (int i = heapsize / 2 - 1; i >= 0; i--) {
			System.out.println("i:" + i);
			Maxify(i);// 依次向上将当前子树最大堆化
		}
	}

	public void HeapSort() {
		for (int i = 0; i < heap.length; i++) {
			// 执行n次，将每个当前最大的值放到堆末尾
			int tmp = heap[0];
			heap[0] = heap[heapsize - 1];
			heap[heapsize - 1] = tmp;
			heapsize--;
			Maxify(0);
		}
	}

	public void Maxify(int i) {
		int l = Left(i);
		int r = Right(i);
		int largest;

		if (l < heapsize && heap[l] > heap[i])
			largest = l;
		else
			largest = i;
		if (r < heapsize && heap[r] > heap[largest])
			largest = r;
		if (largest == i || largest >= heapsize)// 如果largest等于i说明i是最大元素
												// largest超出heap范围说明不存在比i节点大的子女
			return;
		int tmp = heap[i];// 交换i与largest对应的元素位置，在largest位置递归调用maxify
		heap[i] = heap[largest];
		heap[largest] = tmp;
		Maxify(largest);
	}

//	public void IncreaseValue(int i, int val) {
//		heap[i] = val;
//		if (i >= heapsize || i <= 0 || heap[i] >= val)
//			return;
//		int p = Parent(i);
//		if (heap[p] >= val)
//			return;
//		heap[i] = heap[p];
//		IncreaseValue(p, val);
//	}

	private int Parent(int i) {
		return (i - 1) / 2;
	}

	private int Left(int i) {
		return 2 * (i + 1) - 1;
	}

	private int Right(int i) {
		return 2 * (i + 1);
	}
}

 

package org.ewell.spd;

public class HeapSort {
	public static void main(String[] args) {
		int[] array = new int[] { 90, 1, 2, 3, 4, 33 };
		heapSort(array);
		for (int i : array) {
			System.out.println(i);
		}
	}

	public static void heapSort(int[] elements) {
		for (int i = elements.length - 1; i > 0; i--) {
			buildHeap(elements, i); // 建堆
			swap(elements, 0, i); // 交换根节点和最后一个节点
		}
	}

	private static void buildHeap(int[] elements, int lastIndex) {
		int lastParentIndex = (lastIndex - 1) / 2; // 获得最后一个父节点
		System.out.println("lastParentIndex " + lastParentIndex);
		for (int i = lastParentIndex; i >= 0; i--) {
			int parent = elements[i];
			int leftChild = elements[i * 2 + 1]; // 左节点肯定存在
			int rightChild = leftChild;
			if (i * 2 + 2 <= lastIndex) {
				rightChild = elements[i * 2 + 2]; // 右节点不一定存在
			}
			int maxIndex = leftChild < rightChild ? i * 2 + 2 : i * 2 + 1;
			if (parent < elements[maxIndex]) {
				swap(elements, i, maxIndex);
			}
		}
	}

	private static void swap(int[] elements, int firstIndex, int secondIndex) {
		int temp = elements[firstIndex];
		elements[firstIndex] = elements[secondIndex];
		elements[secondIndex] = temp;
	}
}