[Data Structure] Implementation and Stack of Size

Heap generally refers to a binary heap, the structure is as follows

The number inside the circle refers to the subscript, and the content outside the circle, as shown in the figure, cannot be called a pile. , Because it does not satisfy the composition of a large heap or a small heap, the short answer introduction and implementation of the large heap and the small heap are introduced below

The large heap means that the number of each parent node is greater than its own The value of each child node

The algorithm used is to move the large number up and loop to complete the pile

 void Adjustup(size_t child) {Compare com; size_t parent =(child-1)/2; while(child>0) {if(com(_a[child],_a[parent])) {swap (_a[parent],_a[child]); child=parent; parent=(child-1)/2;} else {break;}} }

The process is as shown below

The first exchange of 33 and 43;

The second exchange of 43 and 12;

The third exchange of 33 and 12;< /p>

The fourth exchange of 23 and 8;

The algorithm for small heaps is as follows, using large numbers to cycle down conversion

void Adjustdown(size_t parent) {size_t child =parent*2+1; while(child<_a.size()) {Compare com; if(child+1<_a.size ()&&com(_a[child+1],_a[child]) ) {++child;} if(com(_a[child],_a[parent])) {swap(_a[parent],_a[child]); parent=child; child=parent*2+1;} else {break;}} }

The loop is as follows

The first exchange of 33 and 5,

The second time Exchange 12 and 5,

The third exchange of 4 and 8,

The fourth exchange of 5 and 4

Heap sorting algorithm is as follows

< p>

 void HeapSort(T* a,size_t size) {_a.reserve(size); for(size_t i=0;i=0;--i) {Adjustdown(i);} print(_a,size ); }

All code

#include #include #include#include using namespace std;templatestruct Big{ bool operator()(const T& l,const T& r) {return l>r; }};templatestruct Less{ bool operator()(const T& l,const T& r) {return l class Compare>class He ap//Two fork heap {public: Heap() {} void HeapSort(T* a,size_t size) {_a.reserve(size); for(size_t i=0;i=0;--i) {Adjustdown(i);} print(_a,size);} void Adjustup (size_t child) {Compare com; size_t parent =(child-1)/2; while(child>0) {if(com(_a[child],_a[parent])) {swap(_a[parent ],_a[child]); child=parent; parent=(child-1)/2;} else {break;}}} void Adjustdown(size_t parent) {size_t child =parent*2+1; while(child< _a.size()) {Compare com; if(child+1<_a.size()&&com(_a[child+1],_a[child])) {++child;} if(com(_a [child],_a[parent])) {swap(_a[parent],_a[child]); parent=child; child=parent*2+1;} else {break;}}} bool Empty() {return _a.size()==0;} T& top() {assert(!_a.empty()); return _a[0];} void Push(const T& x) {_a.push_back(x); size_t _size= _a.size(); Adjustup(_size-1); print(_a,_size);} void Pop() {size_t _size=_a.size(); assert(_ size>0); swap(_a[0],_a[_size-1]); _a.pop_back(); _size=_a.size(); Adjustdown(0); print(_a,_size);} void print( vector a,size_t size) {for(int i=0;i _a ;};

Test case

void test(){ int Tree[]={23,12 ,33,45,15,46,17,78,59}; Heap h1; h1.HeapSort(Tree,sizeof(Tree)/sizeof(Tree[0]));}void test2(){ int arr[] = {12, 10, 43, 23, 22, 45, 67,9 }; Heap h1; h1.HeapSort(arr, sizeof(arr)/sizeof(arr[0])) ; Heap h2; h2.HeapSort(arr, sizeof(arr)/sizeof(arr[0])); }