成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（十一）二叉堆

MartinHan / 3070人閱讀

摘要：二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效快速的找出最大值和最小值，常應用于優(yōu)先隊列和著名的堆排序算法中。

二叉堆數(shù)據(jù)結(jié)構(gòu)是一種特殊的二叉樹，他能高效、快速的找出最大值和最小值，常應用于優(yōu)先隊列和著名的堆排序算法中。

二叉堆

二叉堆有以下兩個特性：

是一顆完全二叉樹，表示數(shù)的每一層都有左側(cè)和右側(cè)子節(jié)點（除最后一層的葉節(jié)點），并且最后一層的葉節(jié)點盡可能是左側(cè)子節(jié)點

二叉堆不是最小堆就是最大堆，所有節(jié)點都大于等于（最大堆）或者小于等于（最小堆）每個他的子節(jié)點。

創(chuàng)建最小堆類 
class MinHeap {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.heap = [];
  }
}
二叉堆的數(shù)組表示 
    static getLeftIndex(index) {
    return (2 * index) + 1;
  }

  static getRightIndex(index) {
    return (2 * index) + 2;
  }

  static getParentIndex(index) {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  size() {
    return this.heap.length;
  }

  isEmpty() {
    return this.size() <= 0;
  }

  clear() {
    this.heap = [];
  }
查找二叉堆最小值或者最大值 
 findMinimum() {
    return this.isEmpty() ? undefined : this.heap[0];
  }
交換函數(shù)實現(xiàn) 
function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}
向堆中插入新值 
insert(value) {
    if (value != null) {
      const index = this.heap.length;
      this.heap.push(value);
      this.siftUp(index);
      return true;
    }
    return false;
  };
//上移操作
siftUp(index) {
    let parent = this.getParentIndex(index);
    while (
      index > 0
      && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
    ) {
      swap(this.heap, parent, index);
      index = parent;
      parent = this.getParentIndex(index);
    }
  }
二叉堆中導出最大值或最小值 
extract() {
    if (this.isEmpty()) {
      return undefined;
    }
    if (this.size() === 1) {
      return this.heap.shift();
    }
    const removedValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.siftDown(0);
    return removedValue;
  };
//下移操作
 siftDown(index) {
    let element = index;
    const left = MinHeap.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();
    if (
      left < size
      && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN
    ) {
      element = left;
    }
    if (
      right < size
      && this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN
    ) {
      element = right;
    }
    if (index !== element) {
      swap(this.heap, index, element);
      this.siftDown(element);
    }
  }
創(chuàng)建最大堆類 
class MaxHeap extends MinHeap {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = compareFn;
    this.compareFn = reverseCompare(compareFn);
  }
}

其他操作跟最小堆類一樣，這里就不多加贅述。

堆排序算法 
heapify(array) {
    if (array) {
      this.heap = array;
    }
    const maxIndex = Math.floor(this.size() / 2) - 1;
    for (let i = 0; i <= maxIndex; i++) {
      this.siftDown(i);
    }
    return this.heap;
  };
 getAsArray() {
    return this.heap;
  };
//構(gòu)建最大堆函數(shù)
function buildMaxHeap(array, compareFn) {
    for (let i = Math.floor(array.length / 2);i >= 0; i -= 1){
      heapify(array, i, array.length, compareFn);
      return array;
    }
  }
//堆排序算法實現(xiàn)
function heapSort(array, compareFn = defaultCompare) {
  let heapSize = array.length;
  //用數(shù)組創(chuàng)建一個最大堆用作源數(shù)據(jù)
  buildMaxHeap(array, compareFn);
  while(heapSize > 1){
    //創(chuàng)建最大堆后，最大的值會被存儲在堆的第一個位置，我們將它替換為堆的最后一個值，將堆的大小-1
    swap(array, 0, --heapSize);
    //將堆的根節(jié)點下移并重復步驟2直到堆的大小為1
    heapify(array, 0, heapSize, compareFn);
  }
  return array;
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/106917.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法學習筆記 - 優(yōu)先隊列、二叉堆、左式堆

    摘要：模型優(yōu)先隊列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)以及找出返回并刪除優(yōu)先隊列中最小的元素。左式堆也是二叉樹，左式堆和二叉堆的唯一區(qū)別是左式堆不是理想平衡，而實際上趨向于非常不平衡。事實上，沿左式堆的右路徑是該堆中的最短路徑。 6.1 模型 優(yōu)先隊列是允許至少下列兩種操作的數(shù)據(jù)結(jié)構(gòu)：insert 以及 deleteMin（找出、返回并刪除優(yōu)先隊列中最小的元素）。 insert 操作等價于 en...

    SunZhaopeng 評論0 收藏0

  • 算法筆記-二叉堆

    摘要：二叉堆的概念二叉堆是一種特殊的二叉樹。二叉堆分為兩種最大堆和最小堆，最大堆的父節(jié)點一定大于其子節(jié)點根節(jié)點最大，最小堆的父節(jié)點小于其子節(jié)點根節(jié)點最小。這是我對二叉堆的理解，如有不對，歡迎指正，我會立即修改，謝謝。 二叉堆的概念 二叉堆是一種特殊的二叉樹。二叉樹是每個節(jié)點只有兩個子節(jié)點的樹（應該都懂吧）。二叉堆分為 兩 種：最大堆和最小堆，最大堆的父節(jié)點一定大于其子...

    MrZONT 評論0 收藏0

  • Python數(shù)據(jù)結(jié)構(gòu)——二叉堆的實現(xiàn)

    摘要：二叉堆的有趣之處在于，其邏輯結(jié)構(gòu)上像二叉樹，卻是用非嵌套的列表來實現(xiàn)。二叉堆結(jié)構(gòu)性質(zhì)為了更好地實現(xiàn)堆，我們采用二叉樹。圖完全二叉樹有意思的是我們用單個列表就能實現(xiàn)完全樹。下列所示的代碼是完全二叉堆的實現(xiàn)。 優(yōu)先隊列的二叉堆實現(xiàn) 在前面的章節(jié)里我們學習了先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)：隊列（Queue）。隊列有一種變體叫做優(yōu)先隊列（Priority Queue）。優(yōu)先隊列的出隊（Dequ...

    stackfing 評論0 收藏0

  • PHP面試：說下什么是堆和堆排序？

    摘要：一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。另外我們還將學習堆排序，并將使用實現(xiàn)堆。堆排序在堆排序中，我們需要用給定的值構(gòu)建一個一個堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構(gòu)建一個堆。 堆是什么？ 堆是基于樹抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...

    twohappy 評論0 收藏0

發(fā)表評論

0條評論

MartinHan

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<