Priority Queue / Heap

Let’s learn about heaps and priority queues in Go.

We'll cover the following

Introduction

Heap is a data structure used to implement the priority queue. In a heap, the data is logically organized as a complete binary tree. A complete binary tree is a binary tree that is filled at all possible levels except the last level. The parent value of each node in a heap is greater (or smaller) than the value of its child nodes.

Types of heaps

There are two types of heap data structures which are briefly described below.

  • Min-heap: Each node’s value should be less than or equal to the values of its children.

  • Max-heap: Each node’s value should be greater than or equal to the values of its children.

Applications of a heap

  • Extraction of minimum and maximum values from a dataset.
  • Sorting data in ascending or descending order.

Let’s look at the illustration of a heap:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.