heap - OpenGenus IQ: Computing Expertise & Legacy

Create a Heap from Array of N integers

In this post, we discuss the heap data structure and how to create a min and max heap from N given integers in form of an Array. Similarly, inserting elements one by one take O(N logN) time but the optimal approach takes O(N) time.

Algorithms

k-th Largest Element in a stream

In this article, we will discuss the problem Kth largest Element in a stream, and understand the different methods that can be used to solve the problem efficiently.

Algorithms

Median in stream of running integers [Explained 3 Algorithms]

Given that integers are being read from a data stream, we need to find the median of all the elements read so far starting from the first integer till the last integer. This is called the Median in Running stream of Integers.

Data Structures

Soft heap

Soft heap is a variant of heap data structure (priority queue). It is a powerful data structure owing to amortized constant time complexity of some basic functions.

Data Structures

Skew Heap

We have explained Skew heap. Skew heap is a special variant of Leftist heap. Leftist heap is in turn, a variant of binary heap. We have given an overview of binary heaps, then discussed leftist heaps and finally talked about skew heaps.

Data Structures

Fibonacci Heap

A Fibonacci heap is a heap data structure similar to the binomial heap. It uses Fibonacci numbers and also used to implement the priority queue element in Dijkstra’s shortest path algorithm which reduces the time complexity from O(m log n) to O(m + n log n)

Data Structures

Max Heap and Min Heap

A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes. The most important property of a min heap is that the node with the smallest, or minimum value, will always be the root node. Max heap is similar

Data Structures

Pairing Heap

Pairing heaps are a type of heap data structures which have fast running time for their operations. They are modificaton of Binomial Heap. Basically it is a type of self adjusting Binomial Heap which adjusts or rearrange themselves during the operations, due to which they remain balanced.

Data Structures

Leftist Heap

A leftist heap is a modification priority queue implemneted with variant of binary heap. Regarding binary heap, it is always a complete binary tree. It has two main properites Mean Heap Property and Heavy on left side and supports common operations in O(log N) time complexity.

Data Structures

Binomial Heap

Binomial Heap is an extension of Binary Heap that provides faster union or merge operation together with other operations provided by Binary Heap. A Binomial Heap is a collection of Binomial trees. Binomial Heap is used to implement priority queues.