[Data Structure] Heap, Heap Realization Priority Queue, Stack Sort

1. What is a heap?

Heap is a data structure. The bottom layer is an array object. It can be regarded as a complete binary tree structure.

The largest heap: each parent node is larger than the child node ; Minimum heap: each parent node is smaller than the child node.

2. Binary tree storage of heap data structure.

As shown in the figure, it is a big pile, and it can only ensure that the parent node is larger than the child node. So subscript 0 is the largest in the entire heap, but it is impossible to determine which data with subscript 1,2 is greater

3. Code for heap data structure and priority queue Realization

Idea: start from the subscript of the first non-child node and adjust downwards, to ensure that the parent node is greater than the child node or exchange. (Big pile), the small pile is the opposite. Therefore, the template parameters of functors and templates are used here, so that the code can be reused. According to the passed parameters, it is determined whether it is a large pile or a small pile. Advantage. If it is C, I can only honestly write the similar code again.

#include#include#includeusing namespace std;templatestruct Grearer{ bool operator()(const T& left, const T& right) {return left> right; }};templatestruct Less{ bool operator()(const T& left, const T& right) {return left > //The template parameter of the template, the default value is greater than class Heap{public: Heap() {} Heap(T * a, size_t size) //Build a heap {for (size_t i = 0; i = 0; i--) //Adjust downward from the last non-leaf node {_AjustDown(i);}} void Push(const T& x) {_a.push_back(x) ; //Insert to the last position of the heap first _AjustUp(_a.size()-1); //Then adjust the last data upward} void Pop() {assert(!_a.empty()); // Assert the empty heap swap(_a[0], _a[_a.size()-1]); //Swap the first data and the last of the heap _a.pop_back(); //Equivalent to deleting the first Data _AjustDown(0); //Adjust down the data just placed in the first position} si ze_t Size() //Number of heap nodes {return _a.size();} const T& Top() //The first data of the heap {return _a[0];} bool Empty() //Whether the heap is empty { return _a.empty(); }protected: void _AjustUp(int root) //Adjust up {size_t child = root; size_t parient = (child-1) / 2; while (child> 0) {Compare com; //if (_a[child]> _a[parient]) if (com(_a[child], _a[parient])) {swap(_a[child], _a[parient]);} else {break;} child = parient; parient = (child-1) / 2;}} void _AjustDown(int root) //Adjust down {size_t parient = root; size_t child = 2 * parient + 1; while (child<_a.size()) {Compare com; if ((child+1<_a.size())&&com(_a[child + 1], _a[child])) //Here must first consider the absence of the right child {++child; } //if (_a[parient] <_a[child]) if (com(_a[child], _a[parient])) {swap(_a[parient], _a[child]);} parient = child; child = 2 * parient + 1;} }private: vector_a;};

template>class PriorityQueue //Priority Queue {public: void Push(const T&x) {_h.Push(x);} void Pop() {_h.Pop( );} size_t Size() {return _h.Size();} const T& Top() {return _h.Top();} bool Empty() {return _h.Empty(); }private: Heap _h;};void test(){ int a[10] = {10, 16, 18, 12, 11, 13, 15, 17, 14, 19 }; Heap> hp(a , 10); hp.Push(30); hp.Pop();)void TestPriority() //Test priority queue {PriorityQueue pq; pq.Push(3); pq.Push(2); pq .Push(1); pq.Push(9); cout << pq.Top() << endl; cout << pq.Size() << endl; pq.Pop();
}

4. Heap sorting

Why use heap sorting, because its time complexity is only O(N *lgN), is a better sorting algorithm.

Take ascending order as an example. The basic idea: After building a large heap, exchange the first data of the heap with the last data of the heap, and then the largest number in the entire heap is placed in the last position. Except for the data of 0 in the following table, the rest is satisfied with the big heap, and then the remaining heap is adjusted downward (excluding the last data), and then the data with the subscript as 0 and the second to last data of the heap Exchange, and so on, and finally get an ordered array.
Descending order and vice versa, create a small heap. The algorithm is similar.

Ascending code implementation:

#pragma once# includeusing namespace std;void _AjustDown(int* a, size_t size, int root){ size_t parient = root; size_t child = 2 * parient + 1; while (child a[child])) //Here must first consider the situation that the right child does not exist {++child;} if (a[parient] = 0; i--) //build a big pile {_AjustDown(a, size, i);} for (size_t i = 0; i  


5. Another application of heap-big data operation

such as 100 million Find the largest top 100 numbers among the numbers (can't be stored within 100 million). 
Similar questions can be solved by heap. Take out 100 numbers from 100 million numbers to create a small heap of 100 numbers, read data from the hard disk one by one, if the number read out is greater than the subscript 0 (the smallest number in the heap), insert it into the heap, otherwise discard , The heap of the last 100 data is the largest first 100 among the 100 million numbers.