堆排序
堆是一種完全二叉樹結(jié)構(gòu)毯欣，完全二叉樹就是一種滿二叉樹或者正在變滿的結(jié)構(gòu)。
image-20210225134323949.png
堆分為大根堆和小根堆泉懦，大小的意思是指任意子樹的頭節(jié)點都是這棵子樹中最大或者最小的值的意思蝇刀。
堆結(jié)構(gòu)的維護依賴兩個重要的算法
heapInsert:將一個節(jié)點插入一個已經(jīng)維護好的堆結(jié)構(gòu)中，使其依然是一個堆結(jié)構(gòu)直焙。
heapify(index):一個堆中除了index位置之外的其他地方都符合堆的定義景东，index節(jié)點向下沉，找到自己的位置使得堆結(jié)構(gòu)形成奔誓。
java實現(xiàn)堆結(jié)構(gòu)
public class Heap<T> {
private int size;
private ArrayList<T> elementData = new ArrayList<>();
private Comparator<? super T> comparator;
public Heap(int initialSize) {
elementData = new ArrayList<>(initialSize);
}
public Heap() {
}
public Heap(Comparator<? super T> comparator) {
this.comparator = comparator;
}
private void swap(int aIdx, int bIdx) {
T temp = elementData.get(aIdx);
elementData.set(aIdx, elementData.get(bIdx));
elementData.set(bIdx, temp);
}
@SuppressWarnings("unchecked")
private int compare(T a, T b) {
int result;
if (comparator != null) {
result = comparator.compare(a, b);
} else {
result = ((Comparable<T>) a).compareTo(b);
}
return result;
}
private void heapInsert(int index) {
int fatherIdx;
//找到父親斤吐，如果自己優(yōu)先則交換
while (compare(elementData.get(index), elementData.get(fatherIdx = (index - 1) / 2)) < 0) {
swap(index, fatherIdx);
index = fatherIdx;
}
}
private void heapify(int index) {
if (index < 0) return;
//首先得有左孩子，一個孩子都沒有不用往下找了
int leftChild;
while ((leftChild = (index << 1) | 1) < size) {//index*2+1
int largest = leftChild + 1 < size && compare(elementData.get(leftChild + 1), elementData.get(leftChild)) < 0 ? leftChild + 1 : leftChild;
largest = compare(elementData.get(index), elementData.get(largest)) < 0 ? index : largest;
if (largest == index) {
break;
}
swap(index, largest);
index = largest;
}
}
public void add(T value) {
elementData.add(value);
heapInsert(++size - 1);
}
public T poll() {
if (size <= 0) throw new RuntimeException("no more ele...");
final T result = elementData.get(0);
swap(0, size - 1);
elementData.set(size-- - 1, null);//let't GC to work
heapify(0);
return result;
}
public boolean isEmpty() {
return size == 0;
}
}
堆排序的思想就是利用堆的結(jié)構(gòu)特性厨喂，它的頂上的值為最小或者是最大值和措，看你是什么堆。然后將一個數(shù)組形成堆結(jié)構(gòu)后不斷地彈出堆頂放到最后蜕煌，堆size減少到0的時候就是有序的了派阱。
java實現(xiàn)HeapSort
public static void heapSort(int[] ary) {
//變成堆
int heapSize = ary.length;
//1.法一：全部heapInsert，時間復(fù)雜度O(N*logN)
// for (int i = 0; i < ary.length; i++) {
// heapInsert(ary, i);
// }
//2.法二：從后面開始heapify,時間復(fù)雜度O(N)
for(int i = heapSize;i >= 0;i--)
heapify(ary,i,heapSize);
//大根堆斜纪，對頂元素最大
while (heapSize>0) {
swap(ary, 0, --heapSize);
heapify(ary, 0, heapSize);
}
}
public static void heapify(int[] ary, int index, int heapSize) {
int leftChild;
while ((leftChild = (index << 1) | 1) < heapSize) {
int largest = leftChild + 1 < heapSize && ary[leftChild + 1] > ary[leftChild] ? leftChild + 1 : leftChild;
largest = ary[largest] > ary[index] ? largest : index;
if (index == largest) break;
swap(ary, largest, index);
index = largest;
}
}
public static void heapInsert(int[] ary, int index) {
int fatherIdx;
while (ary[index] > ary[(fatherIdx = (index - 1) / 2)]) {
swap(ary, index, fatherIdx);
index = fatherIdx;
}
}
public static void swap(int[] ary, int aIdx, int bIdx) {
int temp = ary[aIdx];
ary[aIdx] = ary[bIdx];
ary[bIdx] = temp;
}
public static int[] copyArray(int[] origin) {
if (origin == null) return null;
int[] newArray = new int[origin.length];
for (int i = 0; i < origin.length; i++)
newArray[i] = origin[i];
return newArray;
}
public static boolean isEqlArray(int[] arrA, int[] arrB) {
if (arrA == arrB) return true;
if (arrA == null || arrB == null) return false;
if (arrA.length != arrB.length) return false;
for (int i = 0; i < arrA.length; i++)
if (arrA[i] != arrB[i]) return false;
return true;
}
public static void main(String[] args) {
int maxSize = 10, maxValue = 100, times = 1000000;
int i = 0;
for (; i < times; i++) {
int[] nums = MathUtil.generalRandomArray(maxSize, maxValue);
int[] cpyNums = copyArray(nums);
heapSort(nums);
Arrays.sort(cpyNums);
if (!isEqlArray(nums, cpyNums)) {
Logger.getGlobal().info(Arrays.toString(nums));
Logger.getGlobal().info(Arrays.toString(cpyNums));
break;
}
}
Logger.getGlobal().info(i == times ? "finish" : "fucking");
Heap<Integer> heap = new Heap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
heap.add(3);
heap.add(4);
heap.add(2);
heap.add(1);
System.out.println(heap.poll());
System.out.println(heap.poll());
System.out.println(heap.poll());
System.out.println(heap.poll());
}
數(shù)組形成堆有兩種方法贫母，一個是從最后一個元素開始做heapify，一個是從第一個元素開始做heapInsert盒刚，為什么heapify的時間復(fù)雜度為O(N)比起heapInsert要好呢腺劣？
因為一個樹中大量的元素是聚集在底部的，所以若是大量的元素進行heapify后移動的少那么時間復(fù)雜度就會低因块。這個會減少常數(shù)項時間橘原，兩種方式最終堆排序的時間復(fù)雜度都是O(N*logN)，因為后面彈出堆頂每次彈完后進行一個heapify，這個時間復(fù)雜度無法優(yōu)化肯定是O(N*logN)
java代碼實現(xiàn)
public static void heapSort(int[] ary) {
//變成堆
int heapSize = ary.length;
//1.法一：全部heapInsert趾断，時間復(fù)雜度O(N*logN)
for (int i = 0; i < ary.length; i++) {
heapInsert(ary, i);
}
//2.法二：從后面開始heapify,時間復(fù)雜度O(N)
// for(int i = heapSize;i >= 0;i--)
// heapify(ary,i,heapSize);
//大根堆拒名，對頂元素最大
while (heapSize>0) {
swap(ary, 0, --heapSize);
heapify(ary, 0, heapSize);
}
}
public static void heapify(int[] ary, int index, int heapSize) {
int leftChild;
while ((leftChild = (index << 1) | 1) < heapSize) {
int largest = leftChild + 1 < heapSize && ary[leftChild + 1] > ary[leftChild] ? leftChild + 1 : leftChild;
largest = ary[largest] > ary[index] ? largest : index;
if (index == largest) break;
swap(ary, largest, index);
index = largest;
}
}
public static void heapInsert(int[] ary, int index) {
int fatherIdx;
while (ary[index] > ary[(fatherIdx = (index - 1) / 2)]) {
swap(ary, index, fatherIdx);
index = fatherIdx;
}
}
public static void swap(int[] ary, int aIdx, int bIdx) {
int temp = ary[aIdx];
ary[aIdx] = ary[bIdx];
ary[bIdx] = temp;
}
public static int[] copyArray(int[] origin) {
if (origin == null) return null;
int[] newArray = new int[origin.length];
for (int i = 0; i < origin.length; i++)
newArray[i] = origin[i];
return newArray;
}
public static boolean isEqlArray(int[] arrA, int[] arrB) {
if (arrA == arrB) return true;
if (arrA == null || arrB == null) return false;
if (arrA.length != arrB.length) return false;
for (int i = 0; i < arrA.length; i++)
if (arrA[i] != arrB[i]) return false;
return true;
}
public static void main(String[] args) {
int maxSize = 10000000, maxValue = 100, times = 1;
int i = 0;
for (; i < times; i++) {
int[] nums = MathUtil.generalRandomArray(maxSize, maxValue);
int[] cpyNums = copyArray(nums);
heapSort(nums);
Arrays.sort(cpyNums);
if (!isEqlArray(nums, cpyNums)) {
Logger.getGlobal().info(Arrays.toString(nums));
Logger.getGlobal().info(Arrays.toString(cpyNums));
break;
}
}
Logger.getGlobal().info(i == times ? "finish" : "fucking");
Heap<Integer> heap = new Heap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
}
