首页 > 代码库 > 数据结构—堆
数据结构—堆
堆是二叉树中的一种,是一种常见的数据结构,具有以下性质:
- 任意节点小于(最小堆)或大于(最大堆)它的所有后裔,最小元或最大元在堆的根上(堆序性)。
- 堆总是一棵完全二叉树
最大堆如图一,最小堆如图二。
最小堆的实现如下:
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 }
数据结构—堆
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。