首页 > 代码库 > 数据结构—堆

数据结构—堆

    堆是二叉树中的一种,是一种常见的数据结构,具有以下性质:

  • 任意节点小于(最小堆)或大于(最大堆)它的所有后裔,最小元或最大元在堆的根上(堆序性)。
  • 堆总是一棵完全二叉树

      最大堆如图一,最小堆如图二。

    

    最小堆的实现如下:

    MinHeap.h

  1 #include "stdafx.h"  2 #include <iostream>  3 using namespace std;  4 template <typename Type>  5 class MinHeap{  6 public:  7     MinHeap(int size):maxSize(size>defaultSize?size:defaultSize),  8         currentSize(0),heap(new Type[maxSize]){}  9     MinHeap(Type array[],int n);   // 用数组初始化堆 10     ~MinHeap(){ 11         delete []heap; 12     } 13 public: 14     bool insertItem(const Type item);   // 插入元素 15     bool deleteItem(const Type item);   // 删除元素 16     bool isEmpty()const{           //判空 17         return currentSize==0; 18     } 19     bool isFull()const{            // 判满 20         return currentSize == maxSize; 21     } 22     void print();   //打印堆 23 private: 24     void adjustHeap(const int start , const int end);  // 调整堆 25 private: 26     static const int defaultSize = 100; 27     const int maxSize; 28     Type *heap; 29     int currentSize; 30 }; 31  32 // 用数组初始化堆 33 template<typename Type> 34 MinHeap<Type>::MinHeap(Type array[],int n) 35     :maxSize(n>defaultSize?n:defaultSize),currentSize(n){ 36     heap = new Type[maxSize]; 37     for(int i = 0 ; i<n ;i++){ 38         heap[i] = array[i]; 39     } 40     int pos = (n-2)/2; 41     while(pos>=0){ 42         adjustHeap(pos,n-1); 43         pos--; 44     } 45 } 46 //  调整堆 47 template <typename Type> 48 void MinHeap<Type>::adjustHeap(const int start , const int end){ 49     int i = start; 50     int j = 2*i+1; 51     Type item = heap[i]; 52     while (j<=end){ 53         if(j<end&&heap[j]>heap[j+1])j++; 54         if(item > heap[j]){ 55             heap[i] = heap[j]; 56             i=j; 57             j=i*2+1; 58         } 59         else break; 60     } 61     heap[i] = item; 62 } 63 // 插入元素 64 template <typename Type> 65 bool MinHeap<Type>::insertItem(const Type item){ 66     if(isFull()){ 67         cout <<"this heap is full ,can‘t insert the element" <<endl; 68         return 0; 69     } 70     heap[currentSize] = item; 71     int j = currentSize, i = (j-1)/2;  72     Type temp = heap[j]; 73     while(j > 0){    74         if(heap[i] <= temp){ 75             break; 76         } 77         else{ 78             heap[j] = heap[i]; 79             j = i; 80             i = (j-1)/2; 81         } 82     } 83     heap[j] = temp; 84     currentSize++; 85     return 1; 86 } 87 // 删除元素 88 template <typename Type> 89 bool MinHeap<Type>::deleteItem(const Type item){ 90     if(isEmpty()){ 91         cout << "this heap is empty "<< endl; 92         return 0; 93     } 94     int pos = 0; 95     for(; pos<currentSize; pos++){ 96         if(heap[pos]==item){ 97             if(pos==currentSize-1)currentSize--; 98             else{ 99                 heap[pos] = heap[currentSize-1];100                 currentSize--;101                 adjustHeap(pos,currentSize);102                 return 1;103             }104         }105         106     }107     return 0;108 }109 // 输出堆110 template <typename Type>111 void MinHeap<Type>::print(){112     cout << "heap";113     for(int i = 0 ; i< currentSize ; i++){114         cout << "->" << heap[i];115     }116     cout << endl;117 }

  测试:

 1 // Heap.cpp : 定义控制台应用程序的入口点。 2 // 3  4 #include "stdafx.h" 5 #include "HeapNode.h" 6  7 int _tmain(int argc, _TCHAR* argv[]) 8 { 9     10     int array[]={8,5,2,3,1,20,6,7,54,9,10};11     MinHeap<int> heap(array,11);12     heap.print();13     heap.insertItem(63);14     heap.print();15     heap.insertItem(0);16     heap.print();17     heap.deleteItem(5);18     heap.print();19     return 0;20 }

 

数据结构—堆