我如何使用C++实现堆数据结构？

Question

使用这个二进制堆的简单示例。我将如何使用C++代码实现这个数据结构。

       1 
          /\ 
          3 6 
          /\ /\ 
          5 9 8 

此外，除了能够轻松访问数组中的最大值或最小值，此数据结构如何有用？

的例子来自于以下链接：http://www.algolist.net/Data_structures/Binary_heap

Answer 1

这里是我的堆最简单的C++实现。代码评论良好。

/* 
Usage: 
heap Heap; 
Heap.clear(); 
Heap.insert(value); 
Heap.remove(); 
Heap.print(); 
*/ 
struct heap { 
    int myarray[NN+1]; // myarray to store the numbers as heap, 1 indexed 
    int n; // the number of nodes in my array 
    heap() { // constructor 
     clear(); // we clear the heap 
    } 
    void clear() { // initialize the heap 
     n = 0; // initially there are no nodes in the heap 
    } 
    void insert(int K) { // inserting an element K in the heap 
     if(n == NN) { // the heap is full 
      printf("cannot insert any more element, the heap is full\n"); 
      return; 
     } 
     ++n; // so, we have a new element, we increased n before adding 
     // the element because we start from index 1 
     myarray[n] = K; // inserted the element at the rightmost position 
     int p = n; // for keeping the current position 
     while(p > 1) { // p = 1 means we are on the root, and its a heap 
      int pr = p/2; // pr is the parent of p 
      if(myarray[pr] > myarray[p]) { // parent is greater than child 
       swap(myarray[pr], myarray[p]); 
       p = pr; // now the new position of the current element is pr 
      } else break; // otherwise its a heap, so we can stop here 
     } 
    } 
    int remove() { // removing the minimum element from the heap 
     if(n == 0) { // is the heap is empty 
      printf("The heap is empty, cannot delete.\n"); 
      return -1; 
     } 
     int K = myarray[1]; // first element in the heap is the minimum 
     myarray[1] = myarray[n]; // brought the last element in 1st position 
     n--; // as we removed one element, now we need to maintain the heap 

     int p = 1; // as we moved the rightmost element in index 1 
     while(2 * p <= n) { // means p has at least one child, if 2*p > n 
      // we are sure that p is in the last level 
      int ch = 2 * p; // contains the index of the child 
      if(2 * p + 1 <= n) { // right child exists 
       if(myarray[ch] > myarray[ch+1]) // right child is smaller 
        // than left child 
        ch++; // ch contains the index of the right child 
      } 
      if(myarray[p] > myarray[ch]) { // so, current node is larger 
       // than its child 
       swap(myarray[p], myarray[ch]); 
       p = ch; // new position of the current element 
      } else break; //current node is smaller than its children, so heap 
     } 
     return K; // as we stored the minimum element in K 
    } 

    void print() { // printing the heap 
     printf("Number of elements: %d\n", n); 
     for(int i = 1; i <= n; i++) printf("%d ", myarray[i]); 
     printf("\n"); 
    } 

    // Time: O(nlogn) 
    // Extra space: O(1) as we will pass the input array as res here 
    void heapSort(int* res) { 
     for(int i = 0, len = n; i < len; ++i) { 
      res[i] = remove(); 
     } 
    } 
}; 

Answer 2

我写下面Java实现它可以帮助你在c++编写代码;

import java.util.Arrays; 

/** 
* Min heap implementation, also caters to duplicate 
*/ 

public class MinHeap {` 

    private int capacity = 10; 
    private int size; 
    int[] items; 

    public MinHeap() { 
     items = new int[capacity]; 
     size = 0; 
    } 

    public void ensureExtraCapacity() { 
     if (size == capacity) { 
      items = Arrays.copyOf(items, capacity * 2); 
      capacity *= 2; 
     } 
    } 

    private int getLeftChildIndex(int index) { 
     return 2 * index + 1; 
    } 

    private int getRightChildIndex(int index) { 
     return 2 * index + 2; 
    } 

    private int getParentIndex(int index) { 
     return (index - 1)/2; 
    } 

    private boolean hasLeftChild(int index) { 
     return size > getLeftChildIndex(index); 
    } 

    private boolean hasRightChild(int index) { 
     return size > getRightChildIndex(index); 
    } 

    private boolean hasParent(int index) { 
     if(index == 0) 
      return false; 
     return getParentIndex(index) >= 0; 
    } 

    private int leftChild(int index) { 
     return items[getLeftChildIndex(index)]; 
    } 

    private int rightChild(int index) { 
     return items[getRightChildIndex(index)]; 
    } 

    private int parent(int index) { 
     return items[getParentIndex(index)]; 
    } 

    private void swapValues(int index1, int index2) { 
     int temp = items[index1]; 
     items[index1] = items[index2]; 
     items[index2] = temp; 
    } 

    public int peek() { 
     if (size == 0) throw new IllegalStateException(); 
     return items[0]; 
    } 

    public int poll() { 
     if (size == 0) throw new IllegalStateException(); 
     int polled = items[0]; 
     items[0] = items[size - 1]; 
     size--; 
     heapifyDown(); 
     return polled; 
    } 

    public void add(int item) { 
     ensureExtraCapacity(); 
     items[size] = item; 
     size++; 
     heapifyUp(); 
    } 

    private void heapifyUp() { 
     int index = size - 1; 
     while (hasParent(index) && parent(index) > items[index]) { 
      swapValues(index, getParentIndex(index)); 
      index = getParentIndex(index); 
     } 
    } 

    private void heapifyDown() { 
     int index = 0; 
     while (hasLeftChild(index)) { 
      int minimumChildIndex = getLeftChildIndex(index); 
      if (hasRightChild(index) && rightChild(index) < leftChild(index)) 
       minimumChildIndex = getRightChildIndex(index); 

      if (items[index] < items[minimumChildIndex]) { 
       break; 
      } else { 
       swapValues(index, minimumChildIndex); 
      } 
      index = minimumChildIndex; 
     } 
    } 

    /* public void printMinHeap() { 
     while (size > 0) { 
      int poll = poll(); 
      System.out.println(poll); 
     } 
    }*/ 

    /* public static void main(String[] args) { 
     MinHeap minHeap = new MinHeap(); 
     minHeap.add(7); 
     minHeap.add(3); 
     minHeap.add(4); 
     minHeap.add(10); 
     minHeap.add(1); 
     minHeap.add(15); 
     minHeap.add(2); 
     minHeap.add(17); 
     minHeap.add(1); 

     minHeap.printMinHeap(); 
    }*/ 
}