# 215.kth-largest-element-in-an-array

By [guanbinrui.eth](https://paragraph.com/@guanbinrui) · 2022-03-21

---

    /*
     * @lc app=leetcode id=215 lang=javascript
     *
     * [215] Kth Largest Element in an Array
     */
    
    // @lc code=start
    
    //#region Heap
    (function() {
      var Heap,
        defaultCmp,
        floor,
        heapify,
        heappop,
        heappush,
        heappushpop,
        heapreplace,
        insort,
        min,
        nlargest,
        nsmallest,
        updateItem,
        _siftdown,
        _siftup;
    
      (floor = Math.floor), (min = Math.min);
    
      /*
                Default comparison function to be used
                */
    
      defaultCmp = function(x, y) {
        if (x < y) {
          return -1;
        }
        if (x > y) {
          return 1;
        }
        return 0;
      };
    
      /*
                Insert item x in list a, and keep it sorted assuming a is sorted.
        
                If x is already in a, insert it to the right of the rightmost x.
        
                Optional args lo (default 0) and hi (default a.length) bound the slice
                of a to be searched.
                */
    
      insort = function(a, x, lo, hi, cmp) {
        var mid;
        if (lo == null) {
          lo = 0;
        }
        if (cmp == null) {
          cmp = defaultCmp;
        }
        if (lo < 0) {
          throw new Error('lo must be non-negative');
        }
        if (hi == null) {
          hi = a.length;
        }
        while (lo < hi) {
          mid = floor((lo + hi) / 2);
          if (cmp(x, a[mid]) < 0) {
            hi = mid;
          } else {
            lo = mid + 1;
          }
        }
        return [].splice.apply(a, [lo, lo - lo].concat(x)), x;
      };
    
      /*
                Push item onto heap, maintaining the heap invariant.
                */
    
      heappush = function(array, item, cmp) {
        if (cmp == null) {
          cmp = defaultCmp;
        }
        array.push(item);
        return _siftdown(array, 0, array.length - 1, cmp);
      };
    
      /*
                Pop the smallest item off the heap, maintaining the heap invariant.
                */
    
      heappop = function(array, cmp) {
        var lastelt, returnitem;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        lastelt = array.pop();
        if (array.length) {
          returnitem = array[0];
          array[0] = lastelt;
          _siftup(array, 0, cmp);
        } else {
          returnitem = lastelt;
        }
        return returnitem;
      };
    
      /*
                Pop and return the current smallest value, and add the new item.
        
                This is more efficient than heappop() followed by heappush(), and can be
                more appropriate when using a fixed size heap. Note that the value
                returned may be larger than item! That constrains reasonable use of
                this routine unless written as part of a conditional replacement:
                    if item > array[0]
                    item = heapreplace(array, item)
                */
    
      heapreplace = function(array, item, cmp) {
        var returnitem;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        returnitem = array[0];
        array[0] = item;
        _siftup(array, 0, cmp);
        return returnitem;
      };
    
      /*
                Fast version of a heappush followed by a heappop.
                */
    
      heappushpop = function(array, item, cmp) {
        var _ref;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        if (array.length && cmp(array[0], item) < 0) {
          (_ref = [array[0], item]), (item = _ref[0]), (array[0] = _ref[1]);
          _siftup(array, 0, cmp);
        }
        return item;
      };
    
      /*
                Transform list into a heap, in-place, in O(array.length) time.
                */
    
      heapify = function(array, cmp) {
        var i, _i, _j, _len, _ref, _ref1, _results, _results1;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        _ref1 = function() {
          _results1 = [];
          for (
            var _j = 0, _ref = floor(array.length / 2);
            0 <= _ref ? _j < _ref : _j > _ref;
            0 <= _ref ? _j++ : _j--
          ) {
            _results1.push(_j);
          }
          return _results1;
        }
          .apply(this)
          .reverse();
        _results = [];
        for (_i = 0, _len = _ref1.length; _i < _len; _i++) {
          i = _ref1[_i];
          _results.push(_siftup(array, i, cmp));
        }
        return _results;
      };
    
      /*
                Update the position of the given item in the heap.
                This function should be called every time the item is being modified.
                */
    
      updateItem = function(array, item, cmp) {
        var pos;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        pos = array.indexOf(item);
        if (pos === -1) {
          return;
        }
        _siftdown(array, 0, pos, cmp);
        return _siftup(array, pos, cmp);
      };
    
      /*
                Find the n largest elements in a dataset.
                */
    
      nlargest = function(array, n, cmp) {
        var elem, result, _i, _len, _ref;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        result = array.slice(0, n);
        if (!result.length) {
          return result;
        }
        heapify(result, cmp);
        _ref = array.slice(n);
        for (_i = 0, _len = _ref.length; _i < _len; _i++) {
          elem = _ref[_i];
          heappushpop(result, elem, cmp);
        }
        return result.sort(cmp).reverse();
      };
    
      /*
                Find the n smallest elements in a dataset.
                */
    
      nsmallest = function(array, n, cmp) {
        var elem, i, los, result, _i, _j, _len, _ref, _ref1, _results;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        if (n * 10 <= array.length) {
          result = array.slice(0, n).sort(cmp);
          if (!result.length) {
            return result;
          }
          los = result[result.length - 1];
          _ref = array.slice(n);
          for (_i = 0, _len = _ref.length; _i < _len; _i++) {
            elem = _ref[_i];
            if (cmp(elem, los) < 0) {
              insort(result, elem, 0, null, cmp);
              result.pop();
              los = result[result.length - 1];
            }
          }
          return result;
        }
        heapify(array, cmp);
        _results = [];
        for (
          i = _j = 0, _ref1 = min(n, array.length);
          0 <= _ref1 ? _j < _ref1 : _j > _ref1;
          i = 0 <= _ref1 ? ++_j : --_j
        ) {
          _results.push(heappop(array, cmp));
        }
        return _results;
      };
    
      _siftdown = function(array, startpos, pos, cmp) {
        var newitem, parent, parentpos;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        newitem = array[pos];
        while (pos > startpos) {
          parentpos = (pos - 1) >> 1;
          parent = array[parentpos];
          if (cmp(newitem, parent) < 0) {
            array[pos] = parent;
            pos = parentpos;
            continue;
          }
          break;
        }
        return (array[pos] = newitem);
      };
    
      _siftup = function(array, pos, cmp) {
        var childpos, endpos, newitem, rightpos, startpos;
        if (cmp == null) {
          cmp = defaultCmp;
        }
        endpos = array.length;
        startpos = pos;
        newitem = array[pos];
        childpos = 2 * pos + 1;
        while (childpos < endpos) {
          rightpos = childpos + 1;
          if (rightpos < endpos && !(cmp(array[childpos], array[rightpos]) < 0)) {
            childpos = rightpos;
          }
          array[pos] = array[childpos];
          pos = childpos;
          childpos = 2 * pos + 1;
        }
        array[pos] = newitem;
        return _siftdown(array, startpos, pos, cmp);
      };
    
      Heap = (function() {
        Heap.push = heappush;
    
        Heap.pop = heappop;
    
        Heap.replace = heapreplace;
    
        Heap.pushpop = heappushpop;
    
        Heap.heapify = heapify;
    
        Heap.updateItem = updateItem;
    
        Heap.nlargest = nlargest;
    
        Heap.nsmallest = nsmallest;
    
        function Heap(cmp) {
          this.cmp = cmp != null ? cmp : defaultCmp;
          this.nodes = [];
        }
    
        Heap.prototype.push = function(x) {
          return heappush(this.nodes, x, this.cmp);
        };
    
        Heap.prototype.pop = function() {
          return heappop(this.nodes, this.cmp);
        };
    
        Heap.prototype.peek = function() {
          return this.nodes[0];
        };
    
        Heap.prototype.contains = function(x) {
          return this.nodes.indexOf(x) !== -1;
        };
    
        Heap.prototype.replace = function(x) {
          return heapreplace(this.nodes, x, this.cmp);
        };
    
        Heap.prototype.pushpop = function(x) {
          return heappushpop(this.nodes, x, this.cmp);
        };
    
        Heap.prototype.heapify = function() {
          return heapify(this.nodes, this.cmp);
        };
    
        Heap.prototype.updateItem = function(x) {
          return updateItem(this.nodes, x, this.cmp);
        };
    
        Heap.prototype.clear = function() {
          return (this.nodes = []);
        };
    
        Heap.prototype.empty = function() {
          return this.nodes.length === 0;
        };
    
        Heap.prototype.size = function() {
          return this.nodes.length;
        };
    
        Heap.prototype.clone = function() {
          var heap;
          heap = new Heap();
          heap.nodes = this.nodes.slice(0);
          return heap;
        };
    
        Heap.prototype.toArray = function() {
          return this.nodes.slice(0);
        };
    
        Heap.prototype.insert = Heap.prototype.push;
    
        Heap.prototype.top = Heap.prototype.peek;
    
        Heap.prototype.front = Heap.prototype.peek;
    
        Heap.prototype.has = Heap.prototype.contains;
    
        Heap.prototype.copy = Heap.prototype.clone;
    
        return Heap;
      })();
    
      // export Heap to current context
      this.Heap = Heap;
    }.call(global));
    //#endregion
    
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    var findKthLargest = function(nums, k) {
      const maxHeap = new Heap((x, y) => y - x);
    
      for (const num of nums) {
        maxHeap.push(num);
      }
      for (let i = 0; i < k - 1; i += 1) {
        maxHeap.pop();
      }
      return maxHeap.pop();
    };
    
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    var findKthLargest = function(nums, k) {
      const minHeap = new Heap();
    
      for (const num of nums) {
        minHeap.push(num);
    
        // only maintains a k size heap
        if (minHeap.size() > k) {
          minHeap.pop();
        }
      }
      return minHeap.top();
    };
    
    /**
     * Quick Sort
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    var findKthLargest = function(nums, k) {
      function swap(l, r) {
        const temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
      }
      function mid(l, r, m) {
        const _l = nums[l];
        const _r = nums[r];
        const _m = nums[m];
    
        if ((_l < _r || _l < _m) && (_l > _r || _l > _m)) {
          return l;
        }
        if ((_r < _l || _r < _m) && (_r > _l || _r > _m)) {
          return r;
        }
        return m;
      }
      function partition(l, r, m) {
        if (l === r) return l;
    
        const p = mid(l, r, m); // swap p to last
    
        if (p !== r) {
          swap(p, r);
        }
    
        let _l = l;
        let _r = r - 1;
    
        while (_l < _r) {
          while (nums[_l] < nums[r]) _l++;
          while (nums[_r] > nums[r]) _r--;
          if (_l < _r) {
            swap(_l, _r);
            _l++;
            _r--;
          }
        }
        // swap p back
        if (nums[_l] <= nums[r]) {
          swap(_l + 1, r);
          return _l + 1;
        }
        swap(_l, r);
        return _l;
      }
      function find(l, r) {
        const m = Math.floor((l + r) / 2);
        const p = partition(l, r, m); // povit index
        const t = nums.length - k; // target index
    
        if (p === t) {
          return nums[p];
        }
        if (p < t) {
          return find(p + 1, r);
        }
        return find(l, p - 1);
      }
      return find(0, nums.length - 1);
    };
    // @lc code=end

---

*Originally published on [guanbinrui.eth](https://paragraph.com/@guanbinrui/215-kth-largest-element-in-an-array)*