Home  >  Article  >  How to determine the heap sequence

How to determine the heap sequence

藏色散人
藏色散人Original
2019-06-13 11:27:4412501browse

How to determine the heap sequence

We know a sequence, such as {100,6070,50,32,65}, how to determine whether it is a heap?

Answer: Treat this sequence as an array-type binary tree. If the root node is i, the left subtree is 2*i, and the right subtree is 2*i 1.

Heap is divided into maximum heap and minimum heap.

1. All parent nodes in the maximum heap are larger than the left subtree and right subtree. For example, if a known sequence is drawn as a heap:

How to determine the heap sequence

So the known sequence is a maximum heap.

2. All parent nodes in the minimum heap are smaller than the left subtree and right subtree, such as {32,50,60,70,100,65}, drawn as a heap:

How to determine the heap sequence

The sequence that meets the above two situations is the heap

The above is the detailed content of How to determine the heap sequence. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn