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

Today, the editor will share with you the relevant knowledge of what the concept of C++ data structure heap is. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

The concept of heap

Heap is a general term for a special kind of data structure in computer science. A heap is usually an array object that can be thought of as a tree, that is, a complete binary tree with a sequential storage structure.

Tip: complete binary tree

Complete binary tree: after numbering a binary tree with depth k and n nodes, the number of each node is the same as that of the full binary tree with depth k in the same position, and this binary tree is called a complete binary tree. [2]

Properties of heap

The value of a node in the heap is always not greater than or less than the value of its parent node

The heap is always a complete binary tree.

Except that the root node and the last left child node can have no sibling node, other nodes must have sibling node.

Maximum and minimum heap

Maximum heap: the key value of the root node is the largest of all the key values of the heap node, and the value of each node is larger than that of its child.

Minimum heap: the key value of the root node is the smallest of all the key values of the heap node, and the value of each node is smaller than that of its child.

The code defines the binary tree of finite array form int Heap [1024]; / / Sequential structure.

If a node is numbered I and there are left and right sons, they correspond to each other.

Heap / left son Heap / / right son

Its parent node

The dynamic array form of the parent node of Heap [iUniver 2]; / / I

In project development, it often appears in the form of dynamic array, which is mainly introduced in this paper.

/ / default capacity # define DEFAULT_CAPCITY 128typedef struct _ Heap {int * arr; / / dynamic array of storage elements int size; / / number of elements int capacity; / / current storage capacity} Heap; operation

Only the InitHeap () function is used for initialization, while AdjustDown () and BuildHeap () are only internal calls when the heap is established.

Adjust the node downwards

Take creating a maximum heap as an example

Change the > = at "judging whether the largest child node is larger than the current parent node" to = 0; iMel -) {AdjustDown (heap, I) } initialization / / initialization heap / / parameters: initialized heap, array of initial data, array size bool InitHeap (Heap & heap, int * orginal, int size) {/ / default quantity is used if the capacity is greater than size, otherwise size int capacity = DEFAULT_CAPCITY > size?DEFAULT_CAPCITY:size; heap.arr = new int [capacity] / / allocate memory. If (! heap.arr) return false; / / if memory allocation fails, False heap.capacity = capacity; / / capacity heap.size = 0 is returned. / / set the number of elements to 0 / / build a heap if (size > 0) {/ * memory copy if the original array exists Copy the element of orginal to the heap array arr size*sizeof (int) is the memory space occupied by the element * / memcpy (heap.arr,orginal, size*sizeof (int)) Heap.size = size; / / resize BuildHeap (heap); / / build heap} return true;} print heap

It is actually a sequence traversal [4]

/ / print heap void PrintHeapAsTreeStyle (Heap hp) {queue que; int r = 0; que.push (r); queue temp; while (! que.empty ()) {r = que.front (); que.pop (); if (r * 2 + 1 < hp.size) temp.push (r * 2 + 1) If (r * 2 + 2 < hp.size) temp.push (r * 2 + 2); if (que.empty ()) {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.