用 JavaScript 实现队列，堆和优先队列

用数组实现队列

enqueue：元素入队
dequeue：元素出队
size：返回队列长度
showHead: 查看队头元素

class Queue {
  constructor() {
    this.dataStore = [];
  }
  enqueue(element) {
    this.dataStore.push(element);
  }
  dequeue() {
    return this.dataStore.shift();
  }
  size() {
    return this.dataStore.length();
  }
  showHead() {
    return this.dataStore[0];
  }
}

用数组和两个指针实现队列

class Queue {
  constructor() {
    this.dataStore = [];
    this.rear = -1; //指向最后一个元素
    this.front = -1; // 指向第一个元素的下标-1
  }
  enqueue(element) {
    // 入队队尾下标+1
    this.dataStore[++this.rear] = element;
  }
  dequeue() {
    // 出队队首下标+1
    if (this.isEmpty()) return;
    return this.dataStore[++this.front];
  }
  size() {
    return this.rear - this.front;
  }
  showHead() {
    // front+1才是队首元素
    if (!this.isEmpty()) return this.dataStore[this.front+1];
  }
  isEmpty() {
    return this.rear === this.front;
  }
}

使用数组实现环形队列

class CircularQueue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.dataStore = [];
    this.rear = 0; //只要rear与front相等就是空队列,初始值无要求
    this.front = 0;
  }
  enqueue(element) {
    // 入队队尾下标+1,取模达到环形队列效果
    if (this.isFull()) {
      return console.log("full");
    }
    this.rear = (this.rear + 1) % this.maxSize;
    this.dataStore[this.rear] = element;
  }
  dequeue() {
    // 出队队首下标+1,取模达到环形队列效果
    if (this.isEmpty()) {
      return console.log("empty");
    }
    this.front = (this.front + 1) % this.maxSize;
    return this.dataStore[this.front];
  }
  size() {
    // 加上maxSize以免出现负数的情况，再取模以免结果大于maxSize
    return (this.rear - this.front + this.maxSize) % this.maxSize;
  }
  showHead() {
    // front+1才是队首元素,同时取模以免溢出
    if (!this.isEmpty()) return this.dataStore[(this.front + 1) % this.maxSize];
  }
  isEmpty() {
    return this.rear === this.front;
  }
  isFull() {
    return (this.rear + 1) % this.maxSize === this.front;
  }
}

把无序数组调整成大顶堆

// 调整位置方法
function shiftDown(start, length, arr) {
    //从上而下调整堆的顺序
    let i = start;
    let j = 2 * i + 1;
    const temp = arr[i];
    while (j < length) {
      if (arr[j] < arr[j + 1] && j < length - 1) j++; //由于是大顶堆，取大的节点
      if (temp < arr[j]) {
        // 如果比开始节点大就往上浮，也可以理解成开始节点比叶子节点小就跟叶子节点换位，一直往下换到正确的位置
        arr[i] = arr[j];
      } else {
        //若左右两个叶子都比根节点小，由于这是个堆结构，它的叶子的叶子节点也会比根节点小，不需要继续调整
        break;
      }
      i = j;
      j = j * 2 + 1;
    }
    arr[i] = temp;
  }
function makeHeap(arr) {
    // 把数组变成大顶堆
    for (let i = ~~(arr.length / 2) - 1; i > -1; i--) {
      //从下而上局部排序，直到把数组排成一个大顶堆
      shiftDown(i, arr.length, arr);
    }
    return arr;
  }

用大顶堆实现堆排序

function createArr(num) {
  const arr = new Array(num);
  for (let i = 0; i < num; i++) {
    arr[i] = ~~(Math.random() * 10000);
  }
  return arr;
}
// 调整位置方法
function shiftDown(start, length, arr) {
    //从上而下调整堆的顺序
    let i = start;
    let j = 2 * i + 1;
    const temp = arr[i];
    while (j < length) {
      if (arr[j] < arr[j + 1] && j < length - 1) j++; //由于是大顶堆，取大的节点
      if (temp < arr[j]) {
        // 如果比开始节点大就往上浮，也可以理解成开始节点比叶子节点小就跟叶子节点换位，一直往下换到正确的位置
        arr[i] = arr[j];
      } else {
        //若左右两个叶子都比根节点小，由于这是个堆结构，它的叶子的叶子节点也会比根节点小，不需要继续调整
        break;
      }
      i = j;
      j = j * 2 + 1;
    }
    arr[i] = temp;
  }
function makeHeap(arr) {
    // 把数组变成大顶堆
    for (let i = ~~(arr.length / 2) - 1; i > -1; i--) {
      //从下而上局部排序，直到把数组排成一个大顶堆
      shiftDown(i, arr.length, arr);
    }
    return arr;
  }  
function heapSort(arr) {
  arr = makeHeap(arr)
  // 依次把最大的元素剔除，然后调整剩余元素，这样可以按大小依次剔除元素，达到排序效果
  for (let j = arr.length - 1; j > 0; j--) {
    //把最大值与末尾调换，去除末尾元素，剩余再次调整成一个大顶堆，
    // 此时首位又是剩余元素的最大值，一直交换调整直到所有元素排序完毕
    const temp = arr[0];
    arr[0] = arr[j];
    arr[j] = temp;
    shiftDown(0, j, arr);
  }
}
// 测试堆排序的时间
const arr = createArr(8000000);
console.time();
heapSort(arr);
console.timeEnd();

用堆实现优先队列

class PriorityQueue {
  constructor(isMax) {
    this.isMax = isMax; // 是否优先最大值出列
    this.arr = [];
  }
  shiftMaxUp() { // 自底向上调整
    const { arr } = this;
    let i = arr.length - 1;
    let j = ~~((i + 1) / 2) - 1;
    let temp = arr[i];
    while (j >= 0) {
      if (temp > arr[j]) {
        arr[i] = arr[j];
      } else {
        break;
      }
      i = j;
      j = j = ~~((j + 1) / 2) - 1;
    }
    arr[i] = temp;
  }
  shiftMinUp() { // 自底向上调整
    const { arr } = this;
    let i = arr.length - 1;
    let j = ~~((i + 1) / 2) - 1;
    let temp = arr[i];
    while (j >= 0) {
      if (temp < arr[j]) {
        arr[i] = arr[j];
      } else {
        break;
      }
      i = j;
      j = j = ~~((j + 1) / 2) - 1;
    }
    arr[i] = temp;
  }
  shiftDownMax() { // 自顶向下调整
    const { arr } = this;
    if (!arr.length) {
      return arr;
    }
    let i = 0;
    let j = 2 * i + 1;
    let temp = arr[0];
    while (j < arr.length) {
      if (arr[j] < arr[j + 1] && j < arr.length - 1) {
        j++;
      }
      if (temp < arr[j]) {
        arr[i] = arr[j];
      } else {
        break;
      }
      i = j;
      j = j * 2 + 1;
    }
    arr[i] = temp;
  }
  shiftDownMin() { // 自顶向下调整
    const { arr } = this;
    if (!arr.length) {
      return arr;
    }
    let i = 0;
    let j = 2 * i + 1;
    let temp = arr[0];
    while (j < arr.length) {
      if (arr[j] > arr[j + 1] && j < arr.length - 1) {
        j++;
      }
      if (temp > arr[j]) {
        arr[i] = arr[j];
      } else {
        break;
      }
      i = j;
      j = j * 2 + 1;
    }
    arr[i] = temp;
  }
  add(num) { // 插入元素的时候在数组最后，也就是在叶子节点，需要往上调整位置
    const { arr, isMax } = this;
    arr.push(num);
    if (isMax) {
      this.shiftMaxUp();
    } else {
      this.shiftMinUp();
    }
  }
  delete() { // 删除时把队尾放到队首，此时可以从上到下调整位置
    const { arr, isMax } = this;
    arr[0] = arr[arr.length - 1];
    arr.pop();
    if (isMax) {
      this.shiftDownMax();
    } else {
      this.shiftDownMin();
    }
  }
  size() {
    return this.arr.length;
  }
  get() {
    return this.arr[0];
  }
}