堆排序
基本知识
堆是一种数据结构，可用用于实现优先队列。最大堆的定义是，对于堆中的任何一个点，它的值都不大于它的父节点，最小堆反之。堆是一个完全二叉树。
*堆的实现方法：数组，二叉树
*优先队列的实现: 数组，顺序数组，链表，堆（时间效率高）
*复杂度: 数组入队O(1),出队O(n),顺序数组相反，堆都是O(lgn)
*优先队列的应用:
- 动态调度操作系统任务
- 服务器回应并发请求
- 角色在视野范围内选择敌人进行攻击
- N个数字中选择M个数，使用优先队列可以将
NlogN的时间复杂度下降到NlogM的时间复杂度
数组实现堆（从1开始）
父子节点关系:
zero-indexed:
left_c = parent * 2 + 1
right_c = parent * 2 + 2
第n个节点的parent = (n - 1) / 2
1.最大堆代码：insert和shiftUp
- 新元素放入最末尾
- 比较 && 交换 up to O(logn)
时间复杂度O(logn)
public class MaxHeap<Item extends Comparable> {
protected int cap;
protected int count;
protected Item[] heap;
// start from index one
public MaxHeap(int cap) {
this.heap = (Item[])new Comparable[cap];
this.cap = cap;
this.count = 0;
}
public int size() {
return this.count;
}
public boolean isEmpty() {
return this.count == 0;
}
public void insert(Item item) {
assert(this.count + 1 <= cap);
heap[count + 1] = item;
this.count++;
shiftUp(this.count);
}
private void shiftUp(int index) {
// parent node less than child node
while (index > 1 && heap[index/2].compareTo(heap[index]) < 0) {
swap(index/2, index);
index /= 2;
}
}
private void swap(int p1, int p2) {
Item temp = heap[p1];
heap[p1] = heap[p2];
heap[p2] = temp;
}
public static void main(String[] args) {
MaxHeap mh = new MaxHeap(100);
System.out.println(mh.size());
System.out.println(mh.isEmpty());
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
int N = 50; // 堆中元素个数
int M = 100; // 堆中元素取值范围[0, M)
for( int i = 0 ; i < N ; i ++ )
maxHeap.insert((int) (Math.random() * M));
System.out.println(maxHeap.size());
System.out.println(Arrays.toString(maxHeap.heap));
}
}
2.remove和shiftDown操作：
- 最末尾元素代替root元素
- 比较 && 交换
时间复杂度O(logn)
public int remove() {
int removedElem = elem[1];
elem[1] = elem[size];
size--;
shiftDown(1);
return removedElem;
}
public void shiftDown(int index) {
while (2 * index <= size) { // if the left child exists
int max = 2 * index; // switch to a new base
if (max + 1 <= size && elem[max] < elem[max + 1]) { // if right child > left child
max += 1; // find the index of the max value
}
if (elem[index] >= elem[max]) {
break; // break if the root value >= max value
}
swap(index, max);
index = max;
}
}
3种Heap sort
1.Naive: 输入一串数组，全部insert，再依次pop
2.Heapify: 堆初始化时进行heapify，也就是先将原数组元素加入到一个新数组中，对length/2之前的节点进行shiftdown操作，需要创建数组副本。heapify的时间复杂度乍一看是O(nlogn)，但其实是O(n)
由交换次数 x 由倒数第二层开始向上每层node数量之和求等比数列证明(latex公式写在inspect中)：
3.In-place heap sort: 将堆中root的最大元素交换到尾部，再对前面n-1个元素进行shiftdown操作，从第0个元素开始向下heapify。
完整代码
import java.util.Arrays;
public class MaxHeap {
private int cap; // initial capacity of the heap
private int size; // current size of the heap
private int[] elem; // elements
public MaxHeap(int cap) {
this.size = 0;
this.cap = cap;
this.elem = new int[cap + 1]; // start from index one
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// One-indexed heapify
public MaxHeap(int[] nums, int length) {
this.size = length;
this.cap = length;
this.elem = new int[length + 1];
for (int i = 0; i < length; i++) {
elem[i + 1] = nums[i]; // put elements into the heap
}
for (int i = length / 2; i >= 1; i--) {
shiftDown(i);
}
System.out.println("Call constructor2, after heapify: " + Arrays.toString(elem));
}
public void insert(int val) {
size++;
elem[size] = val;
shiftUp(size);
}
public void shiftUp(int index) {
// while child val is larger than its parent
while (index > 1 && elem[index] > elem[index / 2]) {
swap(elem, index, index / 2);
index /= 2;
}
}
public int remove() {
// swap the first with the last
int index = 1;
int removedElem = elem[index];
elem[index] = elem[size];
elem[size] = 0;
size--;
shiftDown(index);
return removedElem;
}
public void shiftDown(int index) {
while (2 * index <= size) { // if current element has the left child
int max = 2 * index; // switch to the left child
if (max + 1 <= size && elem[max + 1] > elem[max]) { // if the right child > left child, change index
max++;
}
if (elem[index] >= elem[max]) { // break if curr less than max(left, right)
break;
}
swap(elem, index, max); // swap
index = max; // again
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
// naive
public void heapSort1(int[] nums) {
int length = nums.length;
int[] res = new int[length];
for (int i = 0; i < length; i++) {
insert(nums[i]);
}
for (int i = length - 1; i >= 0; i--) {
res[i] = remove();
}
System.out.println("Heap Sort 1: " + Arrays.toString(res));
}
// use the heapify constructor
public void heapSort2() {
int[] res = new int[size];
for (int i = size - 1; i >= 0; i--) {
res[i] = remove();
}
System.out.println("Heap Sort 2: " + Arrays.toString(res));
}
// in-place heap sort, zero-indexed
public void heapSort3(int[] nums) {
int length = nums.length;
// heapify
for (int i = (length - 1) / 2; i >= 0; i--) {
inplaceShiftDown(nums, length, i);
}
// swap
for (int i = length - 1; i > 0; i--) {
swap(nums, 0, i); // swap the largest to the last place
inplaceShiftDown(nums, i, 0);
}
System.out.println("Heap Sort 3: " + Arrays.toString(nums));
}
public void inplaceShiftDown(int[] nums, int length, int index) {
while (2 * index + 1 < length) {
int max = 2 * index + 1;
if (max + 1 < length && nums[max] < nums[max + 1]) {
max++;
}
if (nums[index] >= nums[max]) break;
swap(nums, index, max);
index = max;
}
}
public static void main(String[] args) {
int[] nums = {50, 34, 20, 12, 11, 6, 8, 1, 8, 6};
MaxHeap heap1 = new MaxHeap(100);
MaxHeap heap2 = new MaxHeap(nums, nums.length);
MaxHeap heap3 = new MaxHeap(100);
// test diff heap sort
heap1.heapSort1(nums);
heap2.heapSort2();
heap3.heapSort3(nums);
}
}
output:
Call constructor2, after heapify: [0, 50, 34, 20, 12, 11, 6, 8, 1, 8, 6]
Heap Sort 1: [1, 6, 6, 8, 8, 11, 12, 20, 34, 50]
Heap Sort 2: [1, 6, 6, 8, 8, 11, 12, 20, 34, 50]
Heap Sort 3: [1, 6, 6, 8, 8, 11, 12, 20, 34, 50]