# Implement Max Heap and Min heap in Java

**Problem statement**:- Implement Max and Min heap. Display elements in Ascending and Descending order. i.e: Max heap will display elements in Descending order and Min heap display elements in Ascending order.

A min-heap is a binary tree such that -

1. the data contained in each node is less than (or equal to) the data in that node’s children.

2. the binary tree is complete.

A max-heap is a binary tree such that -

1. the data contained in each node is greater than (or equal to) the data in that node’s children.

2. the binary tree is complete.

###
**Sample program implementing max and min heap :-
**

public class MaxMeanHeap { public static void main(String[] args) { CustomHeap chmax = new CustomHeap(256, 0); System.out.println("===========Max Heap creation========="); chmax.insert(12); chmax.insert(23); chmax.insert(2); chmax.insert(112); chmax.insert(22); chmax.insert(3); chmax.insert(27); chmax.insert(1); chmax.displayHeap(); System.out.println("===========Min Heap creation========="); CustomHeap chmin = new CustomHeap(256, 1); chmin.insert(12); chmin.insert(23); chmin.insert(2); chmin.insert(112); chmin.insert(112); chmin.insert(2); chmin.insert(53); chmin.displayHeap(); System.out.println("=====Descending order display: Heap sort===="); chmax.printAscOrder(8); System.out.println("======Ascending order dispplay: Heap sort======="); chmin.printDscOrder(7); } } class CustomHeap { int[] heap; int size; int minMaxFlag; public CustomHeap() { } public CustomHeap(int max, int minMaxFlag) { heap = new int[max]; size = 0; this.minMaxFlag = minMaxFlag; } public int getSize() { return size; } int getTop() { int max = Integer.MAX_VALUE; if (size >= 0) { max = heap[0]; } return max; } public int parentIndex(int index) { return (index - 1) / 2; } public int leftChildIndex(int index) { return (2 * index) + 1; } public int rightChildIndex(int index) { return (2 * index) + 2; } public void swap(int index1, int index2) { heap[index1] = heap[index1] ^ heap[index2]; heap[index2] = heap[index1] ^ heap[index2]; heap[index1] = heap[index1] ^ heap[index2]; } public void insert(int element) { if (size == 0) { heap[size++] = element; } else { heap[size] = element; percolateUp(size++); } } // max/min heap based on flag public void percolateUp(int index) { int temp = heap[index]; int parent = parentIndex(index); if (this.minMaxFlag == 0) { while (index > 0 && heap[parent] < temp) { heap[index] = heap[parent]; index = parent; parent = parentIndex(index); } } else { while (index > 0 && heap[parent] > temp) { heap[index] = heap[parent]; index = parent; parent = parentIndex(index); } } heap[index] = temp; } public int remove() { int temp = heap[0]; heap[0] = heap[--size]; percolateDown(0); return temp; } public void percolateDown(int index) { int lcIndex; int rcIndex; int temp = heap[index]; int largeChildIndex; int smallChilIndex; if (minMaxFlag == 0) { while (index < (size / 2)) { lcIndex = leftChildIndex(index); rcIndex = rightChildIndex(index); if (rcIndex < size && heap[lcIndex] < heap[rcIndex]) { largeChildIndex = rcIndex; } else { largeChildIndex = lcIndex; } if (heap[largeChildIndex] <= temp) break; heap[index] = heap[largeChildIndex]; index = largeChildIndex; } } else { while (index < (size / 2)) { lcIndex = leftChildIndex(index); rcIndex = rightChildIndex(index); if (rcIndex < size && heap[lcIndex] > heap[rcIndex]) { smallChilIndex = rcIndex; } else { smallChilIndex = lcIndex; } if (heap[smallChilIndex] >= temp) break; heap[index] = heap[smallChilIndex]; index = smallChilIndex; } } heap[index] = temp; } public void printAscOrder(int n) { for (int i = 0; i < n; i++) { System.out.print(remove() + "\t"); } System.out.println("\n\n"); } public void printDscOrder(int n) { for (int i = 0; i < n; i++) { System.out.print(remove() + "\t"); } } public void displayHeap() { System.out.print("Inserted elements are: "); for (int m = 0; m < size; m++) if (heap[m] != Integer.MAX_VALUE) System.out.print(heap[m] + " "); else System.out.print("-- "); System.out.println(); int nBlanks = 32; int itemsPerRow = 1; int column = 0; int j = 0; // current item String delimeter = "---------------------------------------------"; System.out.println(delimeter); while (size > 0) { if (column == 0) for (int k = 0; k < nBlanks; k++) System.out.print(' '); System.out.print(heap[j]); if (++j == size) // done? break; if (++column == itemsPerRow) { nBlanks /= 2; itemsPerRow *= 2; column = 0; System.out.println(); } else for (int k = 0; k < nBlanks * 2 - 2; k++) System.out.print(' '); } System.out.println("\n" + delimeter); } }

**Explanation**:-

The underlying data structure used for implementing Heap is Array. We have used falg "minMaxFlag" to distinguish between max and min heap.For max heap minMaxFlag = 0 and min heap minMaxFlag =1.

In insert() method, percolateUp() is called.Depending on value of flag "minMaxFlag" - percolate method execute corresponding while loop to maintain corresponding heap property. Similarly, in percolateDown() which is called form remove() method, depending on value of flag "minMaxFlag" while loop executed to maintain heap property.

**Sample output**:-

===========Max Heap creation=========

Inserted elements are: 112 23 27 12 22 2 3 1

---------------------------------------------

112

23 27

12 22 2 3

1

---------------------------------------------

===========Min Heap creation=========

Inserted elements are: 2 23 2 112 112 12 53

---------------------------------------------

2

23 2

112 112 12 53

---------------------------------------------

=====Descending order display: Heap sort====

112 27 23 22 12 3 2 1

======Ascending order dispplay: Heap sort=======

2 2 12 23 53 112 112

Aivivu chuyên vé máy bay, tham khảo

ReplyDeletevé máy bay đi Mỹ giá rẻ

vé máy bay từ california về việt nam

vé máy bay nhật về việt nam

giá vé máy bay từ đức về việt nam

đăng ký bay từ canada về Việt Nam

ve may bay tu han quoc ve viet nam

danh sách khách sạn cách ly đà nẵng

ve may bay chuyen gia sang Viet Nam

This is really nice which is really cool blog and you have really helped a lot of people who visit the blog and give them useful information.

ReplyDeleteData Science Training in Noida

I like to view your web site which is very useful and excellent resource and truly adored reading your posting. Thank you!

ReplyDeleteData Science Course in Gurgaon

Very nice job... Thanks for sharing this amazing and educative blog post!

ReplyDeleteData Science Training in Lucknow

Really this article is truly one of the best in article history and am a collector of old "items" and sometimes read new items if i find them interesting which is one that I found quite fascinating and should be part of my collection. Very good work!

ReplyDeleteData Scientist Course in Gurgaon

Informative Post. The information you have posted is very useful and sites you have referred was good. Thanks for sharing.

ReplyDeleteData Science Course with Placement

You have done a great job and will definitely dig it and personally recommend to my friends. Thank You.

ReplyDeleteData Science Online Training

I want to thank you for your time in this wonderful read which is really appreciable and put you in your favorites to see new things on your blog, a must-have blog!

ReplyDeleteBusiness Analytics Course in Noida

Very great post which I really enjoy reading this and it is not everyday that I have the possibility to see something like this. Thank You.

ReplyDeleteBest Online Data Science Courses

Very interesting blog and lot of the blogs we see these days don't provide anything that interests me but i am really interested in this one just thought I would post and let you know.

ReplyDeleteData Science Training Institute in Noida

Nice Post i have read this article and if I can I would like to suggest some cool tips or advice and perhaps you could write future articles that reference this article. I want to know more!

ReplyDeleteData Analytics Course in Gurgaon

Well done for this excellent article. and really enjoyed reading this article today it might be one of the best articles I have read so far and please keep this work of the same quality.

ReplyDeleteData Analytics Course in Noida

Excellent work done by you once again here and this is just the reason why I’ve always liked your work with amazing writing skills and you display them in every article. Keep it going!

ReplyDeleteData Analytics Courses in Hyderabad