数据结构-最小索引堆

最小索引堆

由于最小堆存在以下问题：

如果数据非常大的情况下，堆中交换元素会消耗大部分的时间
位置改变后，查询元素会变得困难

所以需要通过索引堆来实现，实现之后，现在不是直接交换堆中的元素，而是增加多一个 index 堆，直接对于索引执行操作

代码实现

const MinHeap = require('./min-heap');

class IndexMinHeap { 
  constructor() {
    this.data = [];
    this.index = [];
    this.count = 0;
  }

  getParentIndex(i) {
    return i >> 1;
  }

  getLeftChildIndex(i) {
    return 2 * i + 1;
  }

  getRightChildIndex(i) {
    return 2 * i + 2;
  }

  swap(i, j) {
    const temp = this.index[i];
    this.index[i] = this.index[j];
    this.index[j] = temp;
  }

  insert(item) {
    this.count++;
    this.data[this.count] = item;
    this.index[this.count] = this.count;
    this.shiftUp(this.count);
  }

  shiftUp(i) {
    while (i >= 1) {
      const parentIndex = this.getParentIndex(i);
      if (this.data[this.index[parentIndex]] > this.data[this.index[i]]) {
        this.swap(parentIndex, i);
        this.shiftUp(parentIndex);
      } else {
        break;
      }
    }
  }

  shiftDown(i) {
    while (2 * i <= this.count) {
      const leftChildIndex = this.getLeftChildIndex();
      const rightChildIndex = this.getRightChildIndex();
      let minIndex = leftChildIndex;
      if (this.data[this.index[leftChildIndex]] > this.data[this.index[rightChildIndex]]) {
        minIndex = rightChildIndex;
      }

      if (this.data[this.index[i]] > this.data[this.index[minIndex]]) {
        this.swap(i, minIndex);
        this.shiftDown(minIndex);
      } else {
        break;
      }
    }
  }

  extraMin() {
    const head = this.data[this.index[1]];
    this.index[1] = this.index.pop();
    this.count--;
    this.shiftDown(1);
    return head;
  }
  
  getMin() {
    return this.data[this.index[1]];
  }

  isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }
}

const indexMinHeap = new IndexMinHeap();
indexMinHeap.insert(9);
indexMinHeap.insert(11);
indexMinHeap.insert(5);
console.log(indexMinHeap.data);
console.log(indexMinHeap.index);
console.log(indexMinHeap.extraMin());
indexMinHeap.insert(8);
console.log(indexMinHeap.extraMin());
indexMinHeap.insert(3);
console.log(indexMinHeap.extraMin());

// arr   3 2 1
// index 3 1 2
//  0    1 2 3

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

最小索引堆

CATALOG

FEATURED TAGS

FRIENDS