【堆】703. 数据流中的第K大元素

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用
KthLargest.add，返回当前数据流中第K大的元素。

示例:

int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new
KthLargest(3, arr); kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5 kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8 kthLargest.add(4); // returns 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

该题与topk问题类似，题目要求找到数据流中第K大的元素，因此只需维护一个大小为K的小顶堆，堆顶元素即为第K大的元素。在构造函数中先对堆数组HEAP赋值，然后利用shiftdown操作构建堆，若nums长度大于K则将K后的元素分别进行add操作。

• add函数：首先判断当前堆大小NOWSIZE是否小于K，小于则表示堆还没填满，则将新元素添加到堆数组末尾，然后从末尾开始利用shiftup进行上浮操作，保持堆的属性；若堆已经填满，且新元素大于堆顶元素，则替换堆顶元素，并利用shiftdown进行下沉操作，保持堆的属性。

堆的介绍可参考

class KthLargest {

	private int K, HEAP[], NOWSIZE;

	public KthLargest(int k, int[] nums) {
		K = k;
		HEAP = new int[K];
		NOWSIZE = 0;

		for (int i = 0; i < nums.length && i < K; i++) {
			HEAP[i] = nums[i];
			NOWSIZE++;
		}
		for (int i = NOWSIZE / 2 - 1; i >= 0; i--) {
			/*
			 * adjust heap
			 */
			shiftdown(i);
		}
		if (NOWSIZE < nums.length) {
			/*
			 * add the cut value
			 */
			for (int i = NOWSIZE; i < nums.length; i++) {
				add(nums[i]);
			}
		}
	}

	public int add(int val) {
		if (NOWSIZE < K) {
			HEAP[NOWSIZE] = val;
			shiftup(NOWSIZE);
			NOWSIZE++;
		} else {
			if (val > HEAP[0] && NOWSIZE == K) {
				// replace the top value of heap
				HEAP[0] = val;
				shiftdown(0);
			}
		}
		return HEAP[0];
	}
	
	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 small_ind = ind;
		if (left_child < NOWSIZE && HEAP[small_ind] > HEAP[left_child]) {
			small_ind = left_child;
		}
		if (right_child < NOWSIZE && HEAP[small_ind] > HEAP[right_child]) {
			small_ind = right_child;
		}
		if (small_ind != ind) {
			/*
			 * exchange the father node and child node then call shiftdown again
			 */
			int temp = HEAP[small_ind];
			HEAP[small_ind] = HEAP[ind];
			HEAP[ind] = temp;
			shiftdown(small_ind);
		}
	}

	public void shiftup(int ind) {
		int parent = (ind - 1) / 2;
		if (parent >= 0 && HEAP[parent] > HEAP[ind]) {
			int temp = HEAP[parent];
			HEAP[parent] = HEAP[ind];
			HEAP[ind] = temp;
			shiftup(parent);
		}
	}

}