Browse Prior Art Database

Finding Minimum Element with O(1) complexity from MaxHeap

IP.com Disclosure Number: IPCOM000245184D
Publication Date: 2016-Feb-18
Document File: 4 page(s) / 118K

Publishing Venue

The IP.com Prior Art Database

Abstract

In a binary maxheap, the next node of last element's parent is the first leaf node. We are aware that minimum element will be in leaf nodes only. Since a heap is a complete binary tree, a heap with n elements will have maximum of n/2+1 leaves and n/2 internal nodes. To find the minimum elements in those half leaf nodes, we can traverse the leave nodes by starting at (h→count+1)/2 till the last node. This traversal would give the time complexity of O(n). This article presents an improved and alternative way of getting the minimum element in a maxheap with O(1) time complexity.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 01 of 4

Finding Minimum Element with O(1) complexity from MaxHeap

A heap is a tree with some special properties. The basic requirement of a heap is that the value of a node must be ≥ (or ≤) to the values of its children. This is called heap property.

A heap also has the additional property that all leaves should be at h or h-1 levels (where h is the height of the tree) for some h>0 . That means heap should form a complete binary tree (as shown below).

In the below examples, the left tree is a heap (each element is greater than its children) and right tree is not a heap (since, 1 is greater than 2).

Types of Heaps?

Based on the heap property we can classify the heaps into two types:


Min heap: The value of a node must be less than or equal to the values of its children

1


Page 02 of 4


Max heap: The value of a node must be greater than or equal to the values of its children

Binary Heaps

In binary heap each node may have up to two children. In practice, binary heaps are enough and we concentrate on binary min-heaps and binary max-heaps for remaining discussion.

Representing Heaps


Before looking at heap operations, let us see how to represent heaps. One possibility is using arrays. Since heaps are forming complete binary trees, there will not be any wastage of locations. For the below discussion let us assume that elements are stored in arrays which starts at index 0. The previous max heap can be represented as:

Note: For the remaining discussion let us assume that we are doing manipulations in max heap.

Existing Solutions

For a given min heap the maximum element will always be at leaf only. Now, the next question is how to find the leaf nodes in tree?

2


Page 03 of 4

If we carefully observe, the next node of last elements parent is the first leaf node. S...