国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

MartinHan / 3010人閱讀

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

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

二叉堆

二叉堆有以下兩個(gè)特性：

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

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

創(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ù)實(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);
    }
  }
二叉堆中導(dǎo)出最大值或最小值 
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;
    }
  }
//堆排序算法實(shí)現(xiàn)
function heapSort(array, compareFn = defaultCompare) {
  let heapSize = array.length;
  //用數(shù)組創(chuàng)建一個(gè)最大堆用作源數(shù)據(jù)
  buildMaxHeap(array, compareFn);
  while(heapSize > 1){
    //創(chuàng)建最大堆后，最大的值會(huì)被存儲(chǔ)在堆的第一個(gè)位置，我們將它替換為堆的最后一個(gè)值，將堆的大小-1
    swap(array, 0, --heapSize);
    //將堆的根節(jié)點(diǎn)下移并重復(fù)步驟2直到堆的大小為1
    heapify(array, 0, heapSize, compareFn);
  }
  return array;
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/106917.html

相關(guān)文章

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

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

    SunZhaopeng 評(píng)論0 收藏0

  • 算法筆記-二叉堆

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

    MrZONT 評(píng)論0 收藏0

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

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

    stackfing 評(píng)論0 收藏0

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

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

    twohappy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

MartinHan

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<