com.cosmian.rest.abe.policy

Class BinaryHeap

java.lang.Object

com.cosmian.rest.abe.policy.BinaryHeap

public class BinaryHeap
extends Object

Heap is basically a tree based data structure. It has nodes. Node comprises of certain elements. Every node contains one element. Nodes may have children. If in case there are no children, it is called a Leaf. There are two rules to be followed: - The value of every node must be less or equal to all the values stored in its children. - It has the least possible height. Heaps are extremely efficient in extracting the least or greatest element. Check"https://www.edureka.co/blog/binary-heap-in-java/" for details

Constructor Summary

Constructors

Constructor and Description
BinaryHeap(int capacity) This will initialize our heap with default size.

Method Summary

Modifier and Type	Method and Description
int	delete(int x) This will delete element at index x Complexity: O(log N)
boolean	equals(Object o)
int	findMax() This method returns the max element of the heap.
int	hashCode()
void	insert(int x) This will insert new element in to heap Complexity: O(log N) As worst case scenario, we need to traverse till the root
boolean	isEmpty() This will check if the heap is empty or not Complexity: O(1)
boolean	isFull() This will check if the heap is full or not Complexity: O(1)
static void	main(String[] args)
void	printHeap() This method used to print all element of the heap
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

BinaryHeap

public BinaryHeap(int capacity)

This will initialize our heap with default size.

Parameters:

capacity - the capacity of the heap

Method Detail

isEmpty

public boolean isEmpty()

This will check if the heap is empty or not Complexity: O(1)

Returns:

true if empty

isFull

public boolean isFull()

This will check if the heap is full or not Complexity: O(1)

Returns:

true if full

insert

public void insert(int x)

This will insert new element in to heap Complexity: O(log N) As worst case scenario, we need to traverse till the root

Parameters:

x - the value to insert

delete

public int delete(int x)

This will delete element at index x Complexity: O(log N)

Parameters:

x - the value to delete

Returns:

the key

printHeap

public void printHeap()

This method used to print all element of the heap

findMax

public int findMax()

This method returns the max element of the heap. complexity: O(1)

Returns:

the max element of the heap

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object

main

public static void main(String[] args)