{"id":1003,"date":"2022-09-08T11:43:07","date_gmt":"2022-11-09T23:23:48","guid":{"rendered":"https:\/\/www.silicloud.com\/blog\/uncategorized\/a-binary-tree-with-a-minimum-heap-structure\/"},"modified":"2025-07-18T16:48:57","modified_gmt":"2025-07-18T16:48:57","slug":"a-binary-tree-with-a-minimum-heap-structure","status":"publish","type":"post","link":"https:\/\/www.silicloud.com\/blog\/a-binary-tree-with-a-minimum-heap-structure\/","title":{"rendered":"A Binary Tree with a minimum heap structure."},"content":{"rendered":"

A Min Heap Binary Tree refers to a type of Binary Tree where the root node has the smallest key value among all nodes in the tree.<\/p>\n

The Min Heap property is applicable to all sub-trees in the tree, as stated in the definition above.<\/p>\n

With the exception of the last 2 layers, almost all nodes, except for the final 2 layers, should possess two offspring. Essentially, this resembles a nearly complete binary tree.<\/p>\n

The tree shown below exemplifies a binary tree of minimum heap type, as it complies with the aforementioned two conditions.<\/p>\n

\"Min<\/div>\n

After discussing the concept of a min heap tree, let’s examine the methods of representing it.<\/p>\n

\n

A Min Heap Tree<\/a>‘s depiction.<\/h2>\n

The commonly used format to index a Min Heap Binary Tree is an array representation.<\/p>\n

\n
\n\n\n\n\n\n\n\n\n
<\/th>\n<\/th>\n<\/tr>\n<\/thead>\n
Current Node<\/td>\narr[i]<\/code><\/td>\n<\/tr>\n
Parent Node<\/td>\narr[(i-1)\/2]<\/code><\/td>\n<\/tr>\n
Left Child<\/td>\narr[(2*i) + 1]<\/code><\/td>\n<\/tr>\n
Right Child<\/td>\narr[(2*i )+ 2]<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n

The base of the entire tree can be found at arr[0].<\/p>\n

The pattern in the table above can easily be identified by referring to the indexing displayed in the figure below.<\/p>\n

\"Min<\/div>\n

A Binary Heap array is essentially a Binary Tree that is indexed using a Level Order Traversal.<\/p>\n

\"Min<\/div>\n

The Min Heap Tree is represented in the figure above with an array.<\/p>\n

Now that we’ve discussed the ideas, let’s proceed with putting this into practice using C!<\/p>\n

\n

Executing a Min Heap Tree<\/h2>\n

To construct the Min Heap, we will utilize the array representation. Initially, let us begin creating the Min Heap structure.<\/p>\n

typedef<\/span> struct<\/span> MinHeap<\/span> MinHeap;<\/span>\r\nstruct<\/span> MinHeap<\/span> {<\/span>\r\n    int<\/span>*<\/span> arr;<\/span>\r\n    \/\/ Current Size of the Heap<\/span>\r\n    int<\/span> size;<\/span>\r\n    \/\/ Maximum capacity of the heap<\/span>\r\n    int<\/span> capacity;<\/span>\r\n}<\/span>;<\/span>\r\n<\/code><\/pre>\n
As elements are inserted or deleted, the array of elements will have its size updated.<\/p>\n
The array has a maximum size known as its capacity.<\/p>\n
We have to write certain functions to indicate that we are representing a Min Heap Tree, such as locating the parent and the children.<\/p>\n
int<\/span> parent<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    \/\/ Get the index of the parent<\/span>\r\n    return<\/span> (<\/span>i -<\/span> 1<\/span>)<\/span> \/<\/span> 2<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> left_child<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    return<\/span> (<\/span>2<\/span>*<\/span>i +<\/span> 1<\/span>)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> right_child<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    return<\/span> (<\/span>2<\/span>*<\/span>i +<\/span> 2<\/span>)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> get_min<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    \/\/ Return the root node element,<\/span>\r\n    \/\/ since that's the minimum, by the min-heap<\/span>\r\n    \/\/ property<\/span>\r\n    return<\/span> heap-><\/span>arr[<\/span>0<\/span>]<\/span>;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
We will create functions that are responsible for initializing and deallocating the heap.<\/p>\n
MinHeap*<\/span> init_minheap<\/span>(<\/span>int<\/span> capacity)<\/span> {<\/span>\r\n    MinHeap*<\/span> minheap =<\/span> (<\/span>MinHeap*<\/span>)<\/span> calloc<\/span> (<\/span>1<\/span>,<\/span> sizeof<\/span>(<\/span>MinHeap)<\/span>)<\/span>;<\/span>\r\n    minheap-><\/span>arr =<\/span> (<\/span>int<\/span>*<\/span>)<\/span> calloc<\/span> (<\/span>capacity,<\/span> sizeof<\/span>(<\/span>int<\/span>)<\/span>)<\/span>;<\/span>\r\n    minheap-><\/span>capacity =<\/span> capacity;<\/span>\r\n    minheap-><\/span>size =<\/span> 0<\/span>;<\/span>\r\n    return<\/span> minheap;<\/span>\r\n}<\/span>\r\n\r\nvoid<\/span> free_minheap<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    if<\/span> (<\/span>!<\/span>heap)<\/span>\r\n        return<\/span>;<\/span>\r\n    free<\/span>(<\/span>heap-><\/span>arr)<\/span>;<\/span>\r\n    free<\/span>(<\/span>heap)<\/span>;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
Now that we have that covered, let’s proceed to learn how we can add elements.<\/p>\n
Adding elements to the Min Heap.<\/h2>\n
The algorithm for inserting an element into the tree is straightforward.<\/p>\n
Analyzing the algorithm step by step.<\/p>\n