Definition of heap and its implementation

Minimum heap: Minimum heap is a sequence of key codes {K0, K1… Kn-1}, which has the following characteristics:

  • Ki K2i + 1 or less
  • Ki K2i ten 2 or less
  • Similarly, maximum heap can be defined

The nature of the heap

  • You can see it’s a complete binary tree
  • The data in the heap is locally ordered and the heap is not unique
    • There are no restrictions between sibling nodes
  • The heap is actually a tree from a logical structure

Class Definition of minimum Heap (ADT)

template <class T> class MinHeap { 
private:
    T* heapArray;
    int CurrentSize; 
    int MaxSize;
    void BuildHeap();
public:
    MinHeap(const int n); // Constructor, where n is the maximum number of elements virtual ~MinHeap(){delete []heapArray; }; Bool isLeaf(int pos) const; int leftchild(int pos) const; int rightchild(int pos) const; int parent(int pos) const; bool Remove(int pos, T& node); bool Insert(const T& newNode); T& RemoveMin(a); Void SiftUp(int position); Void SiftDown(int left); void SiftDown(int left); // The filter function left indicates the array subscript to start processing}Copy the code

The heap minimum heap uses SiftDown and SiftUp

template<class T>
void MinHeap<T>::SiftDown(int position){ int i = position; int j = 2*i+1; Temp = headArray[I]; Temp = headArray[I];while(j<CurrentSize){
		if(j<CurrentSize-1 && headArray[j]>headArray[j+1]) j++; // The smallest nodeif(Temp > headArray[j]) { headArray[i] = headArray[j]; // I =j; // I =j; j=2*i+1; // continue to drop &emsp; }else break;
	}
	headArray[j] = Temp;
}

template<class T>
void MinHeap < T > : : SiftUp (int position) {/ / upward from the position began to adjust, make sequence of int temppos = position; Swap T temp=heapArray[temppos];while((temppos>0) && (heapArray[parent(temppos)] > temp)) { heapArray[temppos]=heapArray[parent(temppos)]; temppos=parent(temppos); } heapArray[temppos]=temp; // Find the final position}Copy the code

Minimum heap building process

First, put n keys into a one-dimensional array

  • The whole is not the minimum heap
  • The tree itself is a heap
  • When I ≥[n/2], the subtree rooted in key code Ki is already a heap
  • We start with the penultimate layer, I = [n/ 2-1]
    • Adjust from right to left
  • Until the whole process reaches the root
    • The whole complete binary tree becomes a heap

The implementation is relatively simple: first initialize the heap, then start from the first branch heapArray[CurrentSize/2-1], and gradually adjust the heap of subtrees from the bottom up

template<class T>
void MinHeap<T>::BuildHeap() {for(int i=CurrentSize/2 -1; i>=0; i--){ SiftDown(i); }}Copy the code

Insert:

template <class T>
bool MinHeap<T>::Insert(const T& newNode) {// newNode {if(CurrentSize==MaxSize) return false; HeapArray [CurrentSize]=newNode; SiftUp(CurrentSize); // adjust CurrentSize++ up; }Copy the code

delete

template<class T>
bool MinHeap<T>::Remove(int pos, T& node) {
    if((pos<0)||(pos>=CurrentSize)) 
    return false;
    T temp=heapArray[pos]; 
    heapArray[pos]=heapArray[--CurrentSize]; 
    if(heapArray[parent(pos)]> heapArray[pos]) SiftUp(pos); / / screenelseSiftDown(pos); // Filter down node=temp;return true;
}
Copy the code

Time complexity

Heap construction efficiency analysis n node heap, height D = log2N +1. If the root is layer 0, the number of nodes in layer I is 2i, considering how far an element moves down in the heap.

  • About half of the nodes are d-1 deep and do not move.
  • A quarter of the nodes are d-2 deep, and they can move down at most one level.
  • At each level up in the tree, there are half as many nodes as at the previous level, and the height of the subtree increases by one. Thus the total number of maximum distances the element can move is

The heap is logN deep, so the average and worst times for inserts and deletions are order logN.

Maximum minimum reactor

The ability to maintain both maximum and minimum values in a data structure. The min-max heap is a complete binary tree where each element has a key data member.

The layers of the tree alternate with the smallest and largest layers.

The root is at the lowest level.

Let x be any node of the smallest and largest heap. If x is at the smallest (largest) level, the key of the element in x is the smallest (largest) of all elements in the subtree rooted in x. Nodes in the smallest (largest) layer are called smallest (largest) nodes.

Priority queue (Priority_queue)

As you can see, the heap can be used to implement priority queues.

  • Priority queue
    • Release objects with minimum (large) values as needed
    • Maximum tree, left tall tree HBLT, WBLT, MaxWBLT
  • Changes the priority of objects stored in the priority queue
    • Auxiliary data structures help find objects

C++ priority queue containers, like queues, can only add (insert) elements from the end of the queue and remove elements from the head of the queue. However, it has a feature that the largest element in the queue is always at the head of the queue, so the queue is not first in, first out, but the largest element in the current queue is removed from the queue.

This is similar to sorting the elements in a queue from largest to smallest.

By default, the comparison rules of elements are sorted by the largest element value; Of course, you can override the “<” operator to redefine the comparison rules (i.e., maximum vs. minimum heap).