【堆】建堆、插入、删除、堆排序

参考

堆就是利用数组来实现二叉树，可用于构建优先队列、堆排序、TopK问题等。可分为：

• 最大堆：父节点的值比其子节点大
• 最小堆：父节点的值比其子节点小

堆的根节点存放了最小（或最大）元素，但是其它节点的排序是未知的，即左节点不一定比右节点大（或小），堆的搜索相对于二叉搜索树更慢，二叉搜索树（如AVL）是平衡二叉树，搜索时间复杂度为O(nlogn)，而堆的目的只是为了获得最大（或最小）元素，将其存储在头节点。

实现堆只需要一个顺序存储结构的数组，相对于二叉树而言，空间开销更低，二叉树还需要分配左右指针占用内存更多。

假设父节点的位置为i（节点下标从0开始），则其左孩子位置为2i+1，右孩子位置为2i+2，这种存储方式与完全二叉树使用数组存储是一样的。

1. 建立最大堆
创建堆数组，将给定数组拷贝给堆数组；调整堆，从最后一个非叶节点开始进行shiftdown下滑操作，如下图，从97开始往前调整堆，将当前节点与其孩子节点进行比较，若孩子节点大于父节点，则将父节点下滑，孩子节点上浮

97和65均比孩子节点大不需下浮，节点38比孩子节点97、76都要小，将其与较大的97节点进行交换

交换后需要进行递归，直到下浮的38节点比孩子节点小

最后38节点被交换到了叶子节点

建堆完成后如下

2.插入新节点
在建立最大堆后，插入节点有可能破坏堆的结构，插入的节点被放到堆的尾部，如下，插入节点85，此时85比父节点49大，不满足最大堆结构

此时需要沿着以下路径将节点85上浮shiftup操作

最后85节点调整到如下位置

3.删除根节点
如下删除根节点97

将尾部节点替换到根节点，然后从根节点开始进行shiftdown下滑操作

调整后堆的结构如下，节点49被下浮到第3层

4.JAVA实现

class maxHeap {
	private int MAX_SIZE, NOW_SIZE, HEAP[];

	public maxHeap(int nums[]) {
		/*
		 * Create a heap using nums[]
		 */
		MAX_SIZE = 100;
		HEAP = new int[MAX_SIZE];
		for (int i = 0; i < nums.length; i++) {
			HEAP[i] = nums[i];
			NOW_SIZE++;
		}
		for (int i = NOW_SIZE / 2 - 1; i >= 0; i--) {
			shiftdown(i);
		}
	}

	public void shiftdown(int ind) {
		/*
		 * Sink the node to satisify the HEAP
		 */
		int left_child = 2 * ind + 1;
		int right_child = 2 * ind + 2;
		int large_ind = ind;
		if (left_child < NOW_SIZE && HEAP[large_ind] < HEAP[left_child]) {
			large_ind = left_child;
		}
		if (right_child < NOW_SIZE && HEAP[large_ind] < HEAP[right_child]) {
			large_ind = right_child;
		}
		if (large_ind != ind) {
			/*
			 * exchange the father node and child node then call shiftdown again
			 */
			int temp = HEAP[large_ind];
			HEAP[large_ind] = HEAP[ind];
			HEAP[ind] = temp;
			shiftdown(large_ind);
		}
	}

	public void shiftup(int ind) {
		/*
		 * when insert a value, need to shiftup the node
		 */
		// parent = (ind - 1) / 2
		int parent = (int) (ind - 1) / 2;
		if (parent >= 0 && HEAP[parent] < HEAP[ind]) {
			int temp = HEAP[parent];
			HEAP[parent] = HEAP[ind];
			HEAP[ind] = temp;
			shiftup(parent);
		}
	}

	public void insert(int val) {
		if (NOW_SIZE < MAX_SIZE - 1) {
			HEAP[NOW_SIZE] = val;
			shiftup(NOW_SIZE);
			NOW_SIZE++;
		}
	}

	public void delete() {
		HEAP[0] = HEAP[NOW_SIZE - 1];
		NOW_SIZE--;
		shiftdown(0);
	}

	public void printHeap() {
		for (int i = 0; i < NOW_SIZE; i++)
			System.out.print(HEAP[i] + " ");
		System.out.println();
	}
}

// 测试
public class main {
	public static void main(String[] args) {
		int nums[] = { 1, 2, 7, 9, 3, 8, 5, 6, 7 };
		maxHeap heap = new maxHeap(nums);
		heap.printHeap();

		heap.insert(10);
		heap.printHeap();

		heap.insert(5);
		heap.printHeap();

		heap.delete();
		heap.printHeap();

		heap.delete();
		heap.printHeap();

	}
}

5.堆排序
在建好堆后，可以进一步实现堆排序，由于堆顶始终是最小（或最大）元素，因此每次取出堆顶元素然后将末尾元素替换到堆顶，并从堆顶进行shiftdown下浮操作调堆，即可完成堆排序。