[[353560]]

 堆 Heap

Heap：可以迅速找到一堆數(shù)中的最大或者最小值的數(shù)據(jù)結構。

將根節(jié)點最大的堆叫做大頂堆或大根堆，根節(jié)點最小的堆叫做小頂堆或小根堆。

常見的堆有二叉堆、裴波那契堆等。

堆本身是一個相對比較抽象的數(shù)據(jù)結構，那么它有具體的實現(xiàn)就分為二叉堆(二項堆、Binary)、裴波那契堆(基于樹的)。那么要實現(xiàn)的話一般面試來說或者經(jīng)常會用的話就是二叉堆來實現(xiàn)，當然在工業(yè)級比較牛逼的應用都是裴波那契以及非常嚴格裴波那契。裴波那契堆因為相對比較復雜，你可以不知道去怎么實現(xiàn)，但是你可以看它的時空復雜度更好，它的實現(xiàn)也是基于樹，但是并不少二叉樹而是多叉的。

假設是大頂堆，則常見操作(API):

• find-max：O(1)
• delete-max：O(logN)
• insert(create)：O(logN) or O(1)

“堆” 這種數(shù)據(jù)結構為什么會有用? 在很多線上中的情形經(jīng)常會在使用，比如說經(jīng)常一個數(shù)一個數(shù)的過來，同時還有從另外一邊的化經(jīng)常去刪除一些數(shù)據(jù)，問你這些數(shù)據(jù)里面它最大值是多少?這里的最大值可能就代表優(yōu)先級最高的結點或者是那個數(shù)需要你先處理的，比如說你的任務流里面隨時你要拿出優(yōu)先級最高的任務優(yōu)先處理，那么這種數(shù)據(jù)結構就更加的好用。

有些人可能會想我用數(shù)組來實現(xiàn)可不可以?或者是我直接排序可不可以?這里我們可以思考一下： 假設維護一個數(shù)組，每次有個新元素插入進來，你就需要把整個數(shù)組進行一次所謂的排序，這樣的話時間復雜度就會是 nlogn，這樣的話就是不夠高效的，另外刪除也可能比較麻煩，假設刪除的是最大值或最小值在最后面的話還好，可以是 O(1) 的時間復雜度，但是如果在最前面的話，你就必須把整個數(shù)組最前面元素刪除掉之后，把整個數(shù)組往前挪，這樣時間復雜度又變差了。

不同的實現(xiàn)比較：https://en.wikipedia.org/wiki/Heap_(data_structure)

當你提到“堆” 的時候，不要默認認為是二叉堆，同時你要知道堆的實現(xiàn)又很多種，而二叉堆本身的話只是因為它相對比較容易實現(xiàn)，它的時間效率是堆里面算比較差的。

二叉堆的性質

通過完全二叉樹來實現(xiàn)(注意：不是二叉搜索樹);

什么是完全二叉樹? 就是它的根和每一級結點都是滿的，除了最下面一層葉子結點可能不滿之外，其他上面結點都是滿的。

二叉堆(大頂)它滿足下列性質：

• 性質1：是一顆完全樹;
• 性質2：樹中任意結點的值總數(shù) >= 其子節(jié)點的值;

由于性質2，就可以保證根結點是最大的結點，所以我們訪問最大值就直接返回這個根結點值。這里思考一個問題：為什么要做成樹的結構呢?其實就要方便，因為找最大值是O(1)了是滿足的，但是問題是后續(xù)你要刪除一個元素或者你要添加一個元素，怎么讓這個操作高效，至少是 logn 的。

二叉堆的實現(xiàn)細節(jié)

1. 二叉堆一般都通過 “數(shù)組” 來實現(xiàn)
2. 假設“第一個元素” 在數(shù)組中的索引為 0 的話，則父結點和子結點的位置關系如下：索引為 i 的左孩子的索引是 (2∗i+1);索引為 i 的右孩子的索引是 (2∗i+2);索引為 i 的父結點的索引是 floor((i−1)/2);

因為把一個完全二叉樹依次放到一維數(shù)組里面去，那么它的孩子和父親之間的關系，就可以直接用下班的數(shù)學關系表示了。

 

Insert 插入操作

1. 新元素一律先插入到堆的尾部
2. 依次向上調整整個堆的結構(一直到根即可) HeapifyUp

當這個堆要進行維護操作，也就是插入元素的時候以及你要刪除元素的時候要怎么做?

例子：85 添加到二叉堆中

 操作的細節(jié)分為兩步：

• 第一步：首先把新元素插入到堆的尾部再說;(新的元素可能是特別大或者特別小，那么要做的一件事情就是重新維護一下堆的所有元素，把新元素挪到這個堆的相應的位置)
• 第二步：依次向上調整整個堆的結構，就叫 HeapifyUp

85 按照上面講的先插入到堆的尾部，也就是一維數(shù)組的尾部，一維數(shù)組的尾部的話就上圖的位置，因為這是一個完全二叉樹，所以它的尾部就是50后面這個結點。插進來之后這個時候就破壞了堆，它的每一個結點都要大于它的兒子的這種屬性了，接下來要做的事情就是要把 85 依次地向上浮動，怎么浮動?就是 85 大于它的父親結點，那么就和父親結點進行交換，直到走到根如果大于根的話，就和根也進行交換。

85 再繼續(xù)往前走之后，它要和 80 再進行比較，同理可得：也就是說這個結點每次和它的父親比，如果它大于它的父親的話就交換，直到它不再大于它的父親。 

 

Delete Max 刪除堆頂操作

將堆尾元素替換到頂部(即堆頂被替代刪除掉)

依次從根部向下調整整個堆的結構(一直到堆尾即可) HeapifyDown

例子：90 從二叉堆中刪除

 堆的實現(xiàn)代碼模版

Java 版本

// Java 
 
import java.util.Arrays; 
import java.util.NoSuchElementException; 
 
 
public class BinaryHeap { 
 
 
    private static final int d = 2; 
    private int[] heap; 
    private int heapSize; 
 
 
    /** 
     * This will initialize our heap with default size. 
     */ 
    public BinaryHeap(int capacity) { 
        heapSize = 0; 
        heap = new int[capacity + 1]; 
        Arrays.fill(heap, -1); 
    } 
 
 
    public boolean isEmpty() { 
        return heapSize == 0; 
    } 
 
 
    public boolean isFull() { 
        return heapSize == heap.length; 
    } 
 
 
 
 
    private int parent(int i) { 
        return (i - 1) / d; 
    } 
 
 
    private int kthChild(int i, int k) { 
        return d * i + k; 
    } 
 
 
    /** 
     * Inserts new element in to heap 
     * Complexity: O(log N) 
     * As worst case scenario, we need to traverse till the root 
     */ 
    public void insert(int x) { 
        if (isFull()) { 
            throw new NoSuchElementException("Heap is full, No space to insert new element"); 
        } 
        heap[heapSize] = x; 
        heapSize ++; 
        heapifyUp(heapSize - 1); 
    } 
 
 
    /** 
     * Deletes element at index x 
     * Complexity: O(log N) 
     */ 
    public int delete(int x) { 
        if (isEmpty()) { 
            throw new NoSuchElementException("Heap is empty, No element to delete"); 
        } 
        int maxElement = heap[x]; 
        heap[x] = heap[heapSize - 1]; 
        heapSize--; 
        heapifyDown(x); 
        return maxElement; 
    } 
 
 
    /** 
     * Maintains the heap property while inserting an element. 
     */ 
    private void heapifyUp(int i) { 
        int insertValue = heap[i]; 
        while (i > 0 && insertValue > heap[parent(i)]) { 
            heap[i] = heap[parent(i)]; 
            i = parent(i); 
        } 
        heap[i] = insertValue; 
    } 
 
 
    /** 
     * Maintains the heap property while deleting an element. 
     */ 
    private void heapifyDown(int i) { 
        int child; 
        int temp = heap[i]; 
        while (kthChild(i, 1) < heapSize) { 
            child = maxChild(i); 
            if (temp >= heap[child]) { 
                break; 
            } 
            heap[i] = heap[child]; 
            i = child; 
        } 
        heap[i] = temp; 
    } 
 
 
    private int maxChild(int i) { 
        int leftChild = kthChild(i, 1); 
        int rightChild = kthChild(i, 2); 
        return heap[leftChild] > heap[rightChild] ? leftChild : rightChild; 
    } 
 
 
    /** 
     * Prints all elements of the heap 
     */ 
    public void printHeap() { 
        System.out.print("nHeap = "); 
        for (int i = 0; i < heapSize; i++) 
            System.out.print(heap[i] + " "); 
        System.out.println(); 
    } 
 
 
    /** 
     * This method returns the max element of the heap. 
     * complexity: O(1) 
     */ 
    public int findMax() { 
        if (isEmpty()) 
            throw new NoSuchElementException("Heap is empty."); 
        return heap[0]; 
    } 
 
 
    public static void main(String[] args) { 
        BinaryHeap maxHeap = new BinaryHeap(10); 
        maxHeap.insert(10); 
        maxHeap.insert(4); 
        maxHeap.insert(9); 
        maxHeap.insert(1); 
        maxHeap.insert(7); 
        maxHeap.insert(5); 
        maxHeap.insert(3); 
 
 
        maxHeap.printHeap(); 
        maxHeap.delete(5); 
        maxHeap.printHeap(); 
        maxHeap.delete(2); 
        maxHeap.printHeap(); 
    } 
} 

 C/C++ 版本 

C/C++ 
#include <iostream> 
using namespace std; 
 
class BinaryHeap { 
public: 
    BinaryHeap(int capacity); 
    void insert(int x); 
    int erase(int x); 
    int findMax(); 
    void printHeap(); 
 
    bool isEmpty() { return heapSize == 0; } 
    bool isFull() { return heapSize == capacity; } 
    ~BinaryHeap() { delete[] heap; } 
 
private: 
    void heapifyUp(int i); 
    void heapifyDown(int i); 
    int maxChild(int i); 
 
    int parent(int i) { return (i - 1) / 2; } 
    int kthChild(int i, int k) { return 2 * i + k; } 
 
private: 
    int *heap; 
    int heapSize; 
    int capacity; 
}; 
 
/** 
 * This will initialize our heap with default size. 
*/ 
BinaryHeap::BinaryHeap(int capacity) { 
    this->heapSize = 0; 
    this->capacity = capacity; 
    this->heap = new int[capacity + 5]; 
} 
 
/** 
 * Inserts new element in to heap 
 * Complexity: O(log N) 
 * As worst case scenario, we need to traverse till the root 
 */ 
void BinaryHeap::insert(int x) { 
    try { 
        if (isFull())  
            throw -1; 
         
        heap[heapSize] = x; 
        heapSize ++; 
        heapifyUp(heapSize - 1); 
        return ; 
    } catch (int e) { 
        cout << "Heap is full, No space to insert new element" << endl; 
        exit(-1); 
    } 
} 
 
/** 
 * Deletes element at index x 
 * Complexity: O(log N) 
 */ 
int BinaryHeap::erase(int x) { 
    try { 
        if (isEmpty())  
            throw -1; 
 
        int maxElement = heap[x]; 
        heap[x] = heap[heapSize - 1]; 
        heapSize--; 
        heapifyDown(x); 
        return maxElement; 
    } catch (int e) { 
        cout << "Heap is empty, No element to delete" << endl; 
        exit(-1); 
    } 
} 
 
/** 
 * Maintains the heap property while inserting an element. 
 */ 
void BinaryHeap::heapifyUp(int i) { 
    int insertValue = heap[i]; 
    while (i > 0 && insertValue > heap[parent(i)]) { 
        heap[i] = heap[parent(i)]; 
        i = parent(i); 
    } 
    heap[i] = insertValue; 
} 
 
/** 
 * Maintains the heap property while deleting an element. 
 */ 
void BinaryHeap::heapifyDown(int i) { 
    int child; 
    int temp = heap[i]; 
    while (kthChild(i, 1) < heapSize) { 
        child = maxChild(i); 
        if (temp >= heap[child]) { 
            break; 
        } 
        heap[i] = heap[child]; 
        i = child; 
    } 
    heap[i] = temp; 
} 
 
int BinaryHeap::maxChild(int i) { 
    int leftChild = kthChild(i, 1); 
    int rightChild = kthChild(i, 2); 
    return heap[leftChild] > heap[rightChild] ? leftChild : rightChild; 
} 
 
/** 
 * This method returns the max element of the heap. 
 * complexity: O(1) 
 */ 
int BinaryHeap::findMax() { 
    try { 
        if (isEmpty())  
            throw -1; 
 
        return heap[0]; 
    } catch (int e) { 
        cout << "Heap is empty." << endl; 
        exit(-1); 
    } 
} 
 
/** 
 * Prints all elements of the heap 
 */ 
void BinaryHeap::printHeap() { 
    cout << "nHeap = "; 
    for (int i = 0; i < heapSize; i++) 
        cout << heap[i] << " "; 
    cout << endl; 
    return ; 
} 
 
 
int main() { 
    BinaryHeap maxHeap(10); 
 
    maxHeap.insert(10); 
    maxHeap.insert(4); 
    maxHeap.insert(9); 
    maxHeap.insert(1); 
    maxHeap.insert(7); 
    maxHeap.insert(5); 
    maxHeap.insert(3); 
 
    maxHeap.printHeap(); 
    maxHeap.erase(5); 
    maxHeap.printHeap(); 
    maxHeap.erase(2); 
    maxHeap.printHeap(); 
 
    return 0; 
} 

 Javascript 版本 

// JavaScript 
class BinaryHeap { 
  constructor(compare) { 
    this.data = []; 
    this.compare = compare; 
  } 
 
  insert(value) { 
    this.insertAt(this.data.length, value); 
  } 
 
  insertAt(index, value) { 
    this.data[index] = value; 
    // 對比當前節(jié)點與其父節(jié)點，如果當前節(jié)點更小就交換它們 
    while (index > 0 && this.compare(value, this.data[Math.floor((index - 1) / 2)]) < 0) { 
      this.data[index] = this.data[Math.floor((index - 1) / 2)]; 
      this.data[Math.floor((index - 1) / 2)] = value; 
      index = Math.floor((index - 1) / 2); 
    } 
  } 
 
  delete(index) { 
    if (this.data.length === 0) return; 
 
    let value = this.data[index]; 
    let i = index; 
    // fix heap 
    while (i < this.data.length) { 
      let left = i * 2 + 1; 
      let right = i * 2 + 2; 
      // 沒有左子節(jié)點 
      if (left >= this.data.length) break; 
      // 沒有右子節(jié)點 
      if (right >= this.data.length) { 
        this.data[i] = this.data[left]; 
        i = left; 
        break; 
      } 
      // 比較左右子節(jié)點的大小，更小的補到父節(jié)點 
      if (this.compare(this.data[left], this.data[right]) < 0) { 
        this.data[i] = this.data[left]; 
        i = left; 
      } else { 
        this.data[i] = this.data[right]; 
        i = right; 
      } 
    } 
    // 查看最后的空位是不是最后的葉子節(jié)點 
    if (i < this.data.length - 1) { 
      this.insertAt(i, this.data.pop()); 
    } else { 
      this.data.pop(); 
    } 
    return value; 
  } 
 
  printHeap() { 
    console.log("nHeap = "); 
    console.log(this.data); 
  } 
} 
 
let maxHeap = new BinaryHeap((a, b) => b - a); 
maxHeap.insert(10); 
maxHeap.insert(4); 
maxHeap.insert(9); 
maxHeap.insert(1); 
maxHeap.insert(7); 
maxHeap.insert(5); 
maxHeap.insert(3); 
 
maxHeap.printHeap(); 
maxHeap.delete(5); 
maxHeap.printHeap(); 
maxHeap.delete(2); 
maxHeap.printHeap(); 

 Python 版本 

Python 
import sys  
class BinaryHeap:  
   
    def __init__(self, capacity):  
        self.capacity = capacity  
        self.size = 0 
        self.Heap = [0]*(self.capacity + 1)  
        self.Heap[0] = -1 * sys.maxsize  
        self.FRONT = 1 
   
    def parent(self, pos):  
        return pos//2 
   
    def leftChild(self, pos):  
        return 2 * pos  
   
    def rightChild(self, pos):  
        return (2 * pos) + 1 
   
    def isLeaf(self, pos):  
        if pos >= (self.size//2) and pos <= self.size:  
            return True 
        return False 
   
    def swap(self, fpos, spos):  
        self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]  
   
    def heapifyDown(self, pos):  
   
        if not self.isLeaf(pos):  
            if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or  
               self.Heap[pos] > self.Heap[self.rightChild(pos)]):  
   
                if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:  
                    self.swap(pos, self.leftChild(pos))  
                    self.heapifyDown(self.leftChild(pos))  
   
                else:  
                    self.swap(pos, self.rightChild(pos))  
                    self.heapifyDown(self.rightChild(pos))  
   
    def insert(self, element):  
        if self.size >= self.capacity :  
            return 
        self.size+= 1 
        self.Heap[self.size] = element  
   
        current = self.size  
   
        while self.Heap[current] < self.Heap[self.parent(current)]:  
            self.swap(current, self.parent(current))  
            current = self.parent(current)  
   
    def Print(self):  
        for i in range(1, (self.size//2)+1):  
            print(" PARENT : "+ str(self.Heap[i])+" LEFT CHILD : "+  
                                str(self.Heap[2 * i])+" RIGHT CHILD : "+ 
                                str(self.Heap[2 * i + 1]))  
    
    def minHeap(self):  
   
        for pos in range(self.size//2, 0, -1):  
            self.heapifyDown(pos)  
   
    def delete(self):  
   
        popped = self.Heap[self.FRONT]  
        self.Heap[self.FRONT] = self.Heap[self.size]  
        self.size-= 1 
        self.heapifyDown(self.FRONT)  
        return popped  
    def isEmpty(self): 
        return self.size == 0 
         
    def isFull(self):  
        return self.size == self.capacity 
if __name__ == "__main__":  
       
    print('The minHeap is ')  
    minHeap = BinaryHeap(5) 
    minHeap.insert(5)  
    minHeap.insert(3)  
    minHeap.insert(17)  
    minHeap.insert(10)  
    minHeap.insert(84)  
    minHeap.insert(19)  
    minHeap.insert(6)  
    minHeap.insert(22)  
    minHeap.insert(9)  
    minHeap.minHeap()  
   
    minHeap.Print()  
    print("The Min val is " + str(minHeap.delete()))  

 高頻題目

• 劍指 Offer 40. 最小的k個數(shù)
• 239. 滑動窗口最大值
• 劍指 Offer 49. 丑數(shù)
• 347. 前 K 個高頻元素
• HeapSort ： https://www.geeksforgeeks.org/heap-sort/

總結

如果只是說堆什么?那么它是一個抽象的數(shù)據(jù)結構，表示可以非常迅速地拿到一堆數(shù)里面的最大值或者最小值，它并不少二叉堆，那么二叉堆和其他的各種堆，維基百科里面有詳細說明：https://en.wikipedia.org/wiki/Heap_(data_structure)

注意：二叉堆只是堆的一種實現(xiàn)形式，二叉堆為什么出現(xiàn)得多?是因為它較為常見且簡單，但是它并不是最優(yōu)的實現(xiàn)，正是因為這個原因，所以二叉堆很多時候并不是完全的那么實用，那么如果在工程的代碼里面我們可以直接調 優(yōu)先隊列(priority_queue) 就行了。