Shulou(Shulou.com)06/03 Report--

This article mainly introduces how to achieve heap in programming development, which has a certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading this article.

I. the concept of heap

Heap data structure is an array object, which can be regarded as a complete binary tree structure.

The binary tree storage of the heap structure is:

Maximum heap: each parent node is larger than the child node.

Minimum heap: each parent node is smaller than the child node.

Objects in the stack have a feature: the last object on the stack is always taken out first, which is often referred to as a last-in, first-out (LIFO) queue. Some operations are defined in the stack. The two most important are PUSH and POP. The PUSH operation adds an element to the top of the stack. The POP operation, by contrast, removes an element from the top of the stack and reduces the stack size by one.

Here, storage is implemented with a vector container, which is a template class that can hold objects of any type (but must be of the same class). Vector objects can efficiently add elements at run time, and elements in vector are stored continuously. When the capacity is not enough, it can expand on its own. Therefore, we do not have to consider some other factors such as insufficient capacity when we use push data.

Second, the realization of the heap

The structure of the heap is realized by binary tree.

First, implement a compare. If you implement the size heap, overload the corresponding class operator "()" with the object.

Templatestruct Less {bool operator () (const Tl, const Tr) {return l

< r; }};templatestruct Big{ bool operator()(const T& l, const T& r) { return l >

R;}}

Define a heap first:

Use template parameters of the template:

For example, when the test case is:

Int arr [] = {12, 10, 43, 23, 22, 45, 67, 9}

Heap N (arr, sizeof (arr) / sizeof (arr [0]))

When you give compare as Big, it will sort by large heap.

Heap N (arr, sizeof (arr) / sizeof (arr [0]))

When you give compare as Big, it will sort by small heap.

Template parameters class Heap {public: Heap () {} Heap (T* a, size_t size) {_ a.reserve (size) of template / / template; for (size_t I = 0; I

< size; ++i) { _a.push_back(a[i]); } //建堆 for (int i = (_a.size() -2)/2; i >

= 0;-- I) {_ AdjustDown (I);} Disp (_ a, size) } / / Pop, swap the first one with the last one (so as not to disturb the order of the other sub-heaps), then / / delete the last one, and then have it downgrade the re-adjustment order void Pop () {size_t _ size = _ a.size (); assert (_ size > 0) Swap (_ a [0], _ a [_ size-1]); _ a.pop_back (); _ size = _ a.size (); _ AdjustDown (0); Disp (_ a, _ size) } / / after push a data, let it be up-regulated to adjust the order void Push (const Tx) {_ a.push_back (x); size_t _ size = _ a.size (); _ AdjustUp (_ size-1); Disp (_ a, _ size) } T & Top () {assert (! _ a.empty ()); return _ a [0];} bool empty () {return _ a.size () = = 0 } void Disp (vector a, size_t k) / / print {for (size_t j = 0; j < k; jacks +) {cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.