マツシタのお勉強

Heap Sort in Java

What is Heap

Reference

www.youtube.com

Heap is the tree structure that has two following restrictions.

  1. Binary Tree
  2. Parent node is smaller or bigger than children nodes.

Heap is good at controlling the relation about small and large. So heap is used to sort algorithm called Heap Sort and Priority Queue.

Structure Of Heap

Heap class has a array to store some elements. The index of this array express the position of the Binary Tree. The position of the root node is zero. A relation of parent and children is like this.

  • Current Node Index: i
  • Parent Node Index: (i - 1) / 2
  • Left Child Node Index: 2 * i + 1
  • Right Child Node Index: 2 * i + 2

Functions

Heap class has two mainly functions, void add(int item) and int poll(). In MinHeap that root node is smallest of all nodes case, these functions are defined like this.

  • void add(int item): Insert the item into heap while keeping the above restriction, parent node is smaller or bigger than children nodes.
  • int poll(): Remove root node from heap while keeping the restriction.

Heap structure always have to be keep the restriction. So when we insert or remove item from heap, we have to adjust the tree.

Source Code