[Heap] Kth Largest Element in an Array

215. Kth Largest Element in an Array

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

본 해답에서 필요한 Heap 자료구조는 이전에 필자가 구현한 ADT가 있어서 재활용하였습니다.

function Heap() {
  this.arr = [];  
}

Heap.prototype.swap = function (a, b) {
  const temp = this.arr[a];
  this.arr[a] = this.arr[b];
  this.arr[b] = temp;
}

Heap.prototype.getParentIdx = function (idx) {
  return Math.floor((idx - 1) / 2);
}

Heap.prototype.getLeftChildIdx = function (idx) {
  return (idx * 2) + 1;
}

Heap.prototype.getRightChildIdx = function (idx) {
  return (idx * 2) + 2;
}

Heap.prototype.push = function (e) {
  this.arr[this.arr.length] = e;
  this.bubbleUp(this.arr.length - 1);  
}

Heap.prototype.bubbleUp = function(idx) {
  while(this.arr[this.getParentIdx(idx)] < this.arr[idx]) {
    const parentIdx = this.getParentIdx(idx);
    this.swap(idx, parentIdx);
    idx = parentIdx;
  }
}

Heap.prototype.pop = function() {
  const max = this.arr[0];
  this.arr[0] = this.arr[this.arr.length - 1];

  this.arr.pop();
  this.bubbleDown(0);

  return max;
}

Heap.prototype.bubbleDown = function(idx) {
  while(
    this.arr[this.getLeftChildIdx(idx)] > this.arr[idx]
    || this.arr[this.getRightChildIdx(idx)] > this.arr[idx]
  ) {
    let biggerIdx = this.getLeftChildIdx(idx);

    if(this.arr[this.getRightChildIdx(idx)] > this.arr[biggerIdx]) {
      biggerIdx = this.getRightChildIdx(idx);
    }

    this.swap(idx, biggerIdx);
    idx = biggerIdx;
  }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  const heap = new Heap();

  for(const num of nums) {
    heap.push(num);
  }  

  let ans = 0;

  for(let i = 0; i < k; i++) {
    ans = heap.pop();
  }

  return ans;
};

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

본 프로그램 강의에서 재귀 방법으로 bubbleUp, bubbleDown 메소드를 구현한 설명을 활용하였습니다.

...

Heap.prototype.bubbleUp = function(i) {
  const child = i;
  const parent = Math.floor((i - 1) / 2);

  if(parent >= 0 && this.arr[child] > this.arr[parent]) {
    const tmp = this.arr[child];
    this.arr[child] = this.arr[parent];
    this.arr[parent] = tmp;

    this.bubbleUp(parent);
  }
}

...

Heap.prototype.bubbleDown = function(i) {
  let child = 2 * i + 1;
  const rightChild = 2 * i + 2;

  if(child <= this.arr.length - 1) {
    if(
      rightChild <= this.arr.length - 1 
      && this.arr[rightChild] > this.arr[child]
    ) {
      child = rightChild;
    }

    if(this.arr[i] < this.arr[child]) {
      const tmp = this.arr[i];
      this.arr[i] = this.arr[child];
      this.arr[child] = tmp;

      this.bubbleDown(child);
    }
  }
}

...