Array representation of binary heap

A complete binary tree that follows the heap sorting property is called a binary heap.

According to the sorting method of binary heap, it can be divided into two types:

Minimum heap is a heap in which the value of a node is greater than or equal to the value of its parent node . The root node of a min-heap is the smallest.

Maximum heap is a heap where the value of a node is less than or equal to the value of its parent node. The root node of the max heap is the largest.

The value of a binary heap is usually represented as an array. The array representation of a binary heap is as follows:

• The index of the root element is 0.

• If i is the index of a node in the array, then the indices of other nodes related to that node are as follows:

  • Left child: (2 *i) 1

  • Right child: (2*i) 2

  • ##Parent node: (i-1)/2

Using the above array representation rules, we can represent the heap as an array:

147891112Now, we can discuss the types of sort-based heaps:

• Minimum Heap - The root node has the minimum value. The node's value is greater than the parent node's value.

Example:

##Array representation:

1

4

7

6

9

10

8

• Max Heap

  - The root node has the maximum value. The node's value is less than the parent node's value.

Example:

##Array representation:

11896451

The above is the detailed content of Array representation of binary heap. For more information, please follow other related articles on the PHP Chinese website!