這是什麼？

滿足以下條件，那就是 Heap：

• 如果每個節點的子節點都大於或小於子自己。
• 新增節點時優先填滿階層後才往下一層。

Max Heap（所有子節點都小於自己）

Min Heap（所有子節點都大於自己）

優點在於，因為第二個條件，所以很容易可以轉換成 Array，進而誕生出 Heap Sort。

除此之外，Heap 能夠運用在：

• Graph Algorithm
• K'th Largest Element in an array

刷題：215. Kth Largest Element in an Array

題目

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

思考

這題是最常見運用 Heap 的題目，常見的解法有幾個：

• 使用 Min Heap，當要求第 K 個大項目時，就從中重複相同數量找尋最大的項目。
• 使用 Heap Sort，第一點應用的延伸。
• 使用 Merge Sort
• 使用 Quick Sort
• 使用 Quick Select

這邊用 Min Heap 解題。

解題

JS

class MinHeap {
  /**
   * @param {number} capacity
   * @param {number[]} value
   */
  constructor(capacity) {
    this.capacity = capacity;
    this.value = [];
  }

  /**
   * @param {number} val
   */
  add(val) {
    this.value.push(val);
    this.bubbleUp(this.value.length - 1);
    if (this.value.length > this.capacity) {
      this.remove();
    }
  }

  remove() {
    this.swap(0, this.value.length - 1);
    const min = this.value.pop();
    this.trickleDown(0);
    return min;
  }

  /**
   * @param {number} index
   */
  bubbleUp(index) {
    const parent = (index - 1) >> 1;
    let max = index;

    if (parent >= 0 && this.value[parent] > this.value[max]) {
      max = parent;
    }

    if (max !== index) {
      this.swap(max, index);
      this.bubbleUp(max);
    }
  }

  /**
   * @param {number} index
   */
  trickleDown(index) {
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;
    let min = index;

    if (leftChild < this.value.length && this.value[leftChild] < this.value[min]) {
      min = leftChild;
    }

    if (rightChild < this.value.length && this.value[rightChild] < this.value[min]) {
      min = rightChild;
    }

    if (min !== index) {
      this.swap(min, index);
      this.trickleDown(min);
    }
  }

  /**
   * @param {number} a
   * @param {number} b
   */
  swap(a, b) {
    const temp = this.value[a];
    this.value[a] = this.value[b];
    this.value[b] = temp;
  }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const findKthLargest = (nums, k) => {
  const minHeap = new MinHeap(k);

  for(let n of nums) {
    minHeap.add(n);
  }

  return minHeap.remove();
};

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int item : nums) {
            if (minHeap.size() == k) {
                if (item > minHeap.peek()) {
                    minHeap.remove();
                    minHeap.add(item);
                }
            } else {
                minHeap.add(item);
            }
        }
        return minHeap.remove();
    }
}

C

struct MinHeap
{
    int capacity;
    int size;
    int *elements;
};

struct MinHeap *initialize(int max)
{
    struct MinHeap *heap = (struct MinHeap *)malloc(sizeof(struct MinHeap));
    heap->capacity = max;
    heap->size = 0;
    heap->elements = (int *)malloc((max + 1) * sizeof(int));
    heap->elements[0] = -2147483648;

    return heap;
}

void insert(struct MinHeap *heap, int key)
{
    int i;

    for (i = ++heap->size; heap->elements[i / 2] > key; i = i / 2)
    {
        heap->elements[i] = heap->elements[i / 2];
    }

    heap->elements[i] = key;
}

void delete_min(struct MinHeap *heap)
{
    int i;
    int child;

    int minElement = heap->elements[1];
    int lastElement = heap->elements[heap->size--];

    for (i = 1; 2 * i <= heap->size; i = child)
    {
        child = i * 2;
        if (child != heap->size && heap->elements[child] > heap->elements[child + 1])
        {
            child++;
        }

        if (lastElement > heap->elements[child])
        {
            heap->elements[i] = heap->elements[child];
        }
        else
        {
            break;
        }
    }

    heap->elements[i] = lastElement;
}

int findKthLargest(int *nums, int numsSize, int k)
{
    struct MinHeap *heap = initialize(k);

    for (int i = 0; i < numsSize; ++i)
    {
        if (heap->size < k)
        {
            insert(heap, nums[i]);
        }
        else
        {
            if (heap->elements[1] < nums[i])
            {
                delete_min(heap);
                insert(heap, nums[i]);
            }
            else
            {
                continue;
            }
        }
    }

    return heap->elements[1];
}

看法

三種語言有三種不同想法：

• JS：嘗試製作出 Min Heap Class，實際效率低於內建的 Array.prototype.sort() 以及其他 sort。
• Java：取巧用內建的 MinHeap，實際效率與 JS 相同，低於內建的 Sort 以及其他 sort。
• C：表現與上兩者相似，採用 sort 的表現會比純粹建立 Heap 來得好。

結論

實際刷題讓我有不同的想法，或許這道題目本身適合用 sort 來處理，硬是要用 Heap 處理得到的成果卻不佳。給我的反思是不是每個題目都可以亂用，寫一大串程式碼覺得自己很厲害，實際效率遠不如內建時，就要檢討自己，在判斷上的訓練不足。

中秋假期的第一天，疲勞感湧現zzz