next_permutation.js

function nextPermutation(numbers) {
  const heap = new MaxHeap;

  let i = numbers.length - 1;
  for (; i >= 0; --i) {
    if (heap.peek() > numbers[i]) {
      break;
    }

    heap.push(numbers[i]);
  }

  let swapped = false;
  for (let j = numbers.length - 1; j > i; --j) {
    numbers[j] = heap.pop();
    if (!swapped && i != -1 && numbers[j] <= numbers[i]) {
      swap(numbers, i, j + 1);
      swapped = true;
    }
  }
  if (!swapped && i != -1) {
    swap(numbers, i, i + 1);
  }
}

class MaxHeap {
  constructor() {
    this.values_ = [];
  }

  push(value) {
    this.values_.push(value)
    this.fixUp_(this.values_.length - 1);
  }

  peek() {
    return this.values_[0];
  }

  pop() {
    const max = this.values_[0];
    if (this.values_.length > 1) {
      this.values_[0] = this.values_.pop();
      this.fixDown_(0);
    } else {
      this.values_.pop();
    }
    return max;
  }

  get length() {
    return this.values_.length;
  }

  fixUp_(index) {
    if (index == 0) {
      return;
    }

    const parent = Math.floor((index - 1) / 2);
    if (this.values_[index] > this.values_[parent]) {
      swap(this.values_, index, parent);
      this.fixUp_(parent);
    }
  }

  fixDown_(index) {
    const left = index * 2 + 1;
    const right = index * 2 + 2;

    if (left >= this.values_.length) {
      return;
    } else if (right >= this.values_.length) {
      if (this.values_[left] > this.values_[index]) {
        swap(this.values_, left, index);
      }
      return;
    }

    const leftValue = this.values_[left];
    const rightValue = this.values_[right];

    if (leftValue > rightValue) {
      if (this.values_[left] > this.values_[index]) {
        swap(this.values_, left, index);
        this.fixDown_(left);
      }
    } else {
      if (this.values_[right] > this.values_[index]) {
        swap(this.values_, right, index);
        this.fixDown_(right);
      }
    }
  }
}

function swap(array, i, j) {
  const tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
}