[Data Structure] Heap & Priority Queue

To be honest, when I looked at the data structure before, I didn’t pay more attention to the heap until now… .

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

heap classification;

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

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

Attention: distinguish the difference from the binary sort tree! ! !

Heap also has many applications, such as priority queue, heap sorting and so on. No matter how many applications, a heap is required first.

The bottom layer of the heap is an array. After understanding the STL, the bottom layer can be written as a vector, which can be dynamically increased.

Heap creation: the elements in an array are Adjust down to adjust to a large pile or a small pile.

Down adjustment algorithm:

void _HeapDown(size_t index) {size_t parent = index; size_t child = 0; while (child <_heap.size()) {child = parent * 2 +1; if (child + 1 <_heap.size() && _heap[child] <_heap[child + 1]) ++child; if (child <_heap.size()&&_heap[parent] <_heap[child]) {swap(_heap[parent], _heap[child]); parent = child;} else break;} }

只要一个结点有左右孩子，就得去Compare and see if you need to exchange. It can only start from the first non-leaf node from the bottom.

The heap also has its own Push and Pop operations. Push operation is the same as stack and queue Push, except that it needs to be adjusted to a heap after Push. Pop operation, not

is to delete the last element, but to delete the element with subscript 0.

Pop: swap the last element with the element with subscript 0, delete the last element, and then adopt The algorithm for downward adjustment is adjusted.

Push: Insert a new element at the end of the array, and adjust it with an upward adjustment algorithm.

Up adjustment algorithm:

void _HeapUp(size_t child) { assert(_heap.size()>0); size_t parent = 0; Compare com; while (child> 0) {parent = (child-1) / 2; if (_heap[parent] <_heap[child]) {swap (_heap[parent], _heap[child]);				child = parent;			}			else				break;		}	}

This is easier than adjusting downwards. Starting from a given node, you only need to compare the size relationship between it and its parent (when there are a lot of piles, the parent subscript

The value is less than the value of the child subscript, then exchange, and remember the change of the child value, the same is true for small piles).

Sometimes, we need both a large pile and a small pile. Of course, two classes can be implemented. Big pile and small pile. However, we also found that the largest pile and the small pile are the largest

the difference lies in a node and a child node The size of the relationship, other ideas are the same, the two classes can not achieve the reusability of the code.

Here we use functors, also called function objects, to achieve code reuse.

The code is given below:

templatestruct Less{ bool operator()(const T& l, const T& r) {return l struct Greater{ bool operator()(const T& l, const T& r) {return l> r ; });template>class Heap{public: Heap(T* _a = NULL,size_t size = 0) {for (size_t i = 0; i = 0; --i) {_HeapDown(i);//Adjust down}} void Show () {if (_heap.size()) {for (size_t i = 0; i <_heap.size();++i) cout << _heap[i] << ""; cout << endl;}} void Push(const T& x) {_heap.push_back(x); _HeapUp(_heap.size()-1);} void Pop()//Delete the element at the top of the heap {assert(_heap.size()>0); swap(_heap[0],_heap[_heap.size()-1]); _heap.pop_back(); _HeapDown(0); } size_t Size() {return _heap.size();} const T& Top() {return _heap[0]; }protected: void _HeapDown(size_t index) {size_t parent = index; size_t child = 0; Compare com; while (child <_heap.size()) {child = parent * 2 +1; //if (child + 1 <_heap.size() && _heap[child] <_heap[child + 1]) if (child + 1 < _heap.size() && com(_heap[child+1],_heap[child])) ++child; //if (child <_heap.size()&&_heap[parent] <_heap[child]) if (child < _heap.size() && com(_heap[child],_heap[parent])) {swap(_heap[parent], _heap[child]); parent = child;} else break;}} void _HeapUp(size_t child) { assert(_heap.size()>0); size_t parent = 0; Compare com; while (child> 0) {parent = (child-1) / 2; //if (_heap[parent] <_heap[child]) if(com(_heap[child],_heap[parent])) {swap(_heap[parent], _heap[child]); child = parent;} else break;} }private: vector _heap;};void testHeap(){ int a[] = {3,4,5,1,2,6,7 }; //Test a lot Heap h1(a,7); h1.Sho w(); h1.Push(10); h1.Show(); h1.Pop(); h1.Show(); //Test small heap Heap> h2(a, 7); h2.Show();	h2.Push(0);	h2.Show();	h2.Pop();	h2.Show();}

< p>Here can realize the size heap.

Time complexity:

Build a heap: O(N*lgN)

Insert: 0(lgN)

Delete: O(lgN)

< p>Priority queue:

We know that queue is a first-in-first-out data structure, but sometimes first-in-first-out is not enough for us. We need the element with the highest priority to get out of the queue first

out of the queue, two methods are given below:

Push: When inserting, put the inserted element in the appropriate position according to the priority. Time complexity O(N)

Pop: delete directly from the head of the line. Time complexity O(1)

Push: Insert directly at the end of the line. Time complexity O(1)

Pop: Find the element with the highest priority and delete it. Time complexity O(N)

First This method is more efficient than the second.

And here, the heap is a way to implement priority queues Efficient method;

The code is given below:

< span style="font-family:SimHei; font-size:18px">

template< typename T,typename Compare = Greater>class PriorityQueue{public: PriorityQueue(T* a,size_t size) :_q(a,size) {} void Pop() {_q.Pop();} void Push(const T& x) {_q.Push(x);} const T& Top() {return _q.Top();} void Show() {_q.Show(); }private: Heap _q;}; void testQueue(){ int a[] = {3,4,5,1,2,6,7 }; //Test a small heap PriorityQueue> q1(a,7); q1.Show (); q1.Push(0); q1.Show(); q1.Pop(); q1.Show(); //Test a lot of PriorityQueue q2(a, 7); q2.Show(); q2.Push(10);	q2.Show();	q2.Pop();	q2.Show();}

here you can efficiently implement the priority queue. It should be noted that the member in the constructor must be completed with an initialization list. Here are the necessary

Several situations where the initialization list must be used~~~~