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

This article introduces the relevant knowledge of "the difference between heap and tree in C language". In the operation process of actual cases, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

Take the small root heap as an example. The characteristic of the heap is that the keywords of the parent node must be less than or equal to the keywords of the child node, and the keywords of the two child nodes have no order.

In the binary sorting tree, the keywords of each parent node are greater than the keywords of the left child node and less than the keywords of the right child node j, that is, the keywords of the left and right children of each parent node have an order relationship.

Thus, when a neutral traversal of two trees is performed, the binary sorted tree results in an ordered sequence, not necessarily a heap.

A heap is a special tree in which each node has a value, characterized by the minimum (or maximum) value of the root node, and the two subtrees of the root node are also a heap. Like a pile of things, they are "stacked" from large to small (or from small to large).

Heap is a logical structure, tree is a storage structure, the two are different levels of things, just like "Chinese" and "adults," there is no contradiction.

The word heap reflects a pyramidal feature with a smaller top and a larger bottom.

Heap and tree combine to give birth to a child called treap

The Chinese name is Shudui.

First of all, it has two values per node: value and weight.

Among them, if you only look at weight, meet the characteristics of heap binary heap (father is smaller/larger than son), if you only look at value, meet the sorting binary tree characteristics (the subtree elements rooted by the left son are smaller than the father, and the subtree rooted by the right son is larger than the father)

value is the value to be maintained and weight is the randomly generated value. Because the randomly generated heap makes the whole treap balanced (strictly prove Google Baidu ~), treap is a relatively short implementation of balanced tree ~

End of nonsense, return to topic (inexplicable rhyme)

As long as there is no ring and no direction connected graph is called tree, it is a topological structure with n points n-1 undirected edges connected and any two points connected.

If we choose a node as the root, then the tree is rooted, and we can determine all parent-child relationships by traversing it once.

If each node of a rooted tree has at most two children, then the tree is called a binary tree.

If each node of a binary tree carries a value, and the value of the father is always greater than the value of the son, we call the tree a big-top binary heap; if the father is smaller than the son, it is a small-top binary heap, collectively called a binary heap. (In fact, the word binary is generally omitted, after all, the heap is usually said to be a binary heap, but the heap is more than a binary heap). This is a good property that predestines the heap to be used as a priority queue.

Priority queues support the following operations

1. Put an element in it.

2. Always take out the largest element (the rules for big and small can be defined by a comparison function)

Obviously, heaps can do that.

Of course, as mentioned earlier, there are more complex binomial heaps than binary heaps, Fibonacci heaps, pairing heaps, and so on.

In summary, heaps are a special kind of tree.

Definition of heap: k(i)=k(2i +1) among elements 1 to n/2

* Simply put: if you think of this sequence as a complete binary tree, you want to make this unordered list

* If it becomes a heap, then the left and right child nodes of a node i smaller than or equal to n/2(the last non-terminal node is n/2) are all larger than this node.

* The definition of heap k(i)

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.