廢話不多說，直接代碼， 以后就用這個：
/*author : qiuludate : 2017-03-07*/#ifndef _MIN_HEAP_H#define _MIN_HEAP_H#include<vector>using namespace std;template <class T>class MinHeap{public: MinHeap():m_HeapSize(0){} MinHeap(T nums[], int n); void Push(T elem); T Pop(); void Show();PRivate: vector<T> m_Elem; int m_HeapSize;private: void Down(int idx); void Up(int idx); void Swap(int idx1, int idx2);};#endif // !_MIN_HEAP_H#include "min_heap.h"#include <iostream>template <class T> void MinHeap<T>::Down(int idx){ int son = 2 * idx + 1; if (son < m_HeapSize) { if (son + 1 < m_HeapSize && m_Elem[son] > m_Elem[son+1]) son++; if (m_Elem[idx]>m_Elem[son]) Swap(idx, son); Down(son); }}template <class T>void MinHeap<T>::Swap(int idx1, int idx2){ int temp = m_Elem[idx1]; m_Elem[idx1] = m_Elem[idx2]; m_Elem[idx2] = temp;}template <class T>MinHeap<T>::MinHeap(T nums[], int n){ m_HeapSize = 0; for (int i = 0; i < n; i++) { m_Elem.push_back(nums[i]); m_HeapSize++; } for (int i = m_HeapSize / 2 - 1; i >= 0; i--) Down(i);}template <class T>void MinHeap<T>::Up(int idx){ int f = (idx - 1) / 2; if (idx > 0 && m_Elem[idx] < m_Elem[f]) { Swap(idx, f); Up(f); }}template <class T>void MinHeap<T>::Push(T elem){ m_Elem.push_back(elem); m_HeapSize++; Up(m_HeapSize - 1);}template <class T>T MinHeap<T>::Pop(){ T result = m_Elem[0]; Swap(0, m_HeapSize - 1); m_Elem.pop_back(); m_HeapSize--; Down(0); return result;}template <class T>void MinHeap<T>::Show(){ for (int i = 0; i < m_HeapSize; i++) { std::cout << m_Elem[i] << " "; } std::cout << "/n";}新聞熱點
疑難解答
