template<typename Item> class MaxHeap{ private: Item *data; int count; int capacity; void shiftUp(int k){ while( k > 1 && data[k/2] < data[k] ){ swap( data[k/2], data[k] ); k /= 2; } } public: MaxHeap(int capacity){ data = new Item[capacity+1]; count = 0; this->capacity = capacity; } ~MaxHeap(){ delete[] data; } int size(){ return count; } bool isEmpty(){ return count == 0; } //添加新元素 void insert(Item item){ assert( count + 1 <= capacity ); data[count+1] = item; count ++; shiftUp(count); } public: void testPrint(){ if( size() >= 100 ){ cout<<"Fancy print can only work for less than 100 int"; return; } if( typeid(Item) != typeid(int) ){ cout <<"Fancy print can only work for int item"; return; } cout<<"The Heap size is: "<<size()<<endl; cout<<"data in heap: "; for( int i = 1 ; i <= size() ; i ++ ) cout<<data[i]<<" "; cout<<endl; cout<<endl; int n = size(); int max_level = 0; int number_per_level = 1; while( n > 0 ) { max_level += 1; n -= number_per_level; number_per_level *= 2; } int max_level_number = int(pow(2, max_level-1)); int cur_tree_max_level_number = max_level_number; int index = 1; for( int level = 0 ; level < max_level ; level ++ ){ string line1 = string(max_level_number*3-1, ' '); int cur_level_number = min(count-int(pow(2,level))+1,int(pow(2,level))); bool isLeft = true; for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){ putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft ); isLeft = !isLeft; } cout<<line1<<endl; if( level == max_level - 1 ) break; string line2 = string(max_level_number*3-1, ' '); for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ ) putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 ); cout<<line2<<endl; cur_tree_max_level_number /= 2; } } private: void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){ int sub_tree_width = (cur_tree_width - 1) / 2; int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width; assert(offset + 1 < line.size()); if( num >= 10 ) { line[offset + 0] = '0' + num / 10; line[offset + 1] = '0' + num % 10; } else{ if( isLeft) line[offset + 0] = '0' + num; else line[offset + 1] = '0' + num; } } void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){ int sub_tree_width = (cur_tree_width - 1) / 2; int sub_sub_tree_width = (sub_tree_width - 1) / 2; int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width; assert( offset_left + 1 < line.size() ); int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width; assert( offset_right < line.size() ); line[offset_left + 1] = '/'; line[offset_right + 0] = '\\'; } };
public://获取优先级最高的节点 Item extractMax(){ assert( count > 0 ); Item ret = data[1]; swap( data[1] , data[count] ); count --; shiftDown(1); return ret; } Item getMax(){ assert( count > 0 ); return data[1]; }
private void shiftDown(int k){ while( 2*k <= count ){ int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置 if( j+1 <= count && data[j+1] > data[j] ) j ++; // data[j] 是 data[2*k]和data[2*k+1]中的最大值 if( data[k] >= data[j] ) break; swap( data[k] , data[j] ); k = j; } }
//测试 int main() { MaxHeap<int> maxheap = MaxHeap<int>(100); srand(time(NULL)); for( int i = 0 ; i < 63 ; i ++ ){ maxheap.insert( rand()%100 ); } while( !maxheap.isEmpty() ) cout<<maxheap.extractMax()<<" "; cout<<endl; return 0; }
堆排序：
template<typename T> void heapSort2(T arr[], int n){ MaxHeap<T> maxheap = MaxHeap<T>(arr,n); for( int i = n-1 ; i >= 0 ; i-- ) arr[i] = maxheap.extractMax(); }测试：
int main() { int n = 1000000; // 测试1 一般性测试 cout<<"Test for Random Array, size = "<<n<<", random range [0, "<<n<<"]"<<endl; int* arr1 = SortTestHelper::generateRandomArray(n,0,n); int* arr2 = SortTestHelper::copyIntArray(arr1, n); int* arr3 = SortTestHelper::copyIntArray(arr1, n); int* arr4 = SortTestHelper::copyIntArray(arr1, n); int* arr5 = SortTestHelper::copyIntArray(arr1, n); SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n); SortTestHelper::testSort("Quick Sort", quickSort, arr2, n); SortTestHelper::testSort("Quick Sort 3 Ways", quickSort3Ways, arr3, n); SortTestHelper::testSort("Heap Sort 1", heapSort1, arr4, n); SortTestHelper::testSort("Heap Sort 2", heapSort2, arr5, n); delete[] arr1; delete[] arr2; delete[] arr3; delete[] arr4; delete[] arr5; cout<<endl; // 测试2 测试近乎有序的数组 int swapTimes = 100; cout<<"Test for Random Nearly Ordered Array, size = "<<n<<", swap time = "<<swapTimes<<endl; arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes); arr2 = SortTestHelper::copyIntArray(arr1, n); arr3 = SortTestHelper::copyIntArray(arr1, n); arr4 = SortTestHelper::copyIntArray(arr1, n); arr5 = SortTestHelper::copyIntArray(arr1, n); SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n); SortTestHelper::testSort("Quick Sort", quickSort, arr2, n); SortTestHelper::testSort("Quick Sort 3 Ways", quickSort3Ways, arr3, n); SortTestHelper::testSort("Heap Sort 1", heapSort1, arr4, n); SortTestHelper::testSort("Heap Sort 2", heapSort2, arr5, n); delete[] arr1; delete[] arr2; delete[] arr3; delete[] arr4; delete[] arr5; cout<<endl; // 测试3 测试存在包含大量相同元素的数组 cout<<"Test for Random Array, size = "<<n<<", random range [0,10]"<<endl; arr1 = SortTestHelper::generateRandomArray(n,0,10); arr2 = SortTestHelper::copyIntArray(arr1, n); arr3 = SortTestHelper::copyIntArray(arr1, n); arr4 = SortTestHelper::copyIntArray(arr1, n); arr5 = SortTestHelper::copyIntArray(arr1, n); SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n); SortTestHelper::testSort("Quick Sort", quickSort, arr2, n); SortTestHelper::testSort("Quick Sort 3 Ways", quickSort3Ways, arr3, n); SortTestHelper::testSort("Heap Sort 1", heapSort1, arr4, n); SortTestHelper::testSort("Heap Sort 2", heapSort2, arr5, n); delete[] arr1; delete[] arr2; delete[] arr3; delete[] arr4; delete[] arr5; return 0; }
改进：
public: MaxHeap(int capacity){ data = new Item[capacity+1]; count = 0; this->capacity = capacity; } MaxHeap(Item arr[], int n){ data = new Item[n+1]; capacity = n; for( int i = 0 ; i < n ; i ++ ) data[i+1] = arr[i]; count = n; for( int i = count/2 ; i >= 1 ; i -- ) shiftDown(i); }template<typename T> void heapSort2(T arr[], int n){ MaxHeap<T> maxheap = MaxHeap<T>(arr,n); for( int i = n-1 ; i >= 0 ; i-- ) arr[i] = maxheap.extractMax(); }
转载于:https://www.cnblogs.com/lzb0803/p/9183562.html
相关资源：各显卡算力对照表！