What is a Heap ?

-

A heap is a tree with some special properties. The basic requirement of a heap is that the value of  a node must be greater than equal to  (or  less than equal to) to the values of its children. That is called heap property. Additional property of heap – all leaves should be at h or h-1 (where h is the height of the tree) levels for some h>0 (complete binary tree). That means heap should form a complete binary tree.

 Types of Heap :-
   →  Min Heap : The value of a node must be less than or equal to the values                             of its children.
   →  Max Heap : The value of a node must be greater than or equal to the                                  values of its children.

 Declaration of Heap :-

 public class Heap
{
      int[] array;
      int capacity;
      int count;
      int Heap(int capacity);

 }

 Creating Heap :-

 public Heap(int capacity)
{
      this.count = 0;
      this.capacity = capacity;
      this.array = new int[capacity];
}

Comments

Post a Comment

Popular posts from this blog

How to Build REST API Using PHP

-
Image
Create REST API in PHP API stands for Application Programming Interface and the idea behind API is to connect different applications irrespective of their platforms to share information. Generally, API takes requests from different applications, processes it and gives back the response. What is REST API? REST stands for Representational State Transfer and it means that the request and the response should contain a representation of the information i.e., should be in a certain format. So basically, the requests must use proper HTTP methods and the response must be in a proper format like JSON or XML instead of plain text. REST API is nothing but a normal API with a set of principles. We need to follow a set of rules while creating and consuming REST API. The rules include the following : 1. Use appropriate HTTP methods while performing API calls. The following are the four primary HTTP methods which should be used to send and receive API requests.     ...
Read more

AVL Tree Rotations

-
Image
Rotations When the tree structure changes, we need to modify the tree to restore the AVL tree property. This can be done using single or double rotations. Types of Violations Let us assume the node that must be rebalanced in X. Violations might occur in four cases: Insertion into the left subtree of the left child of X. Insertion into the right subtree of the right child of X.  Insertion into the right subtree of the left child of X. Insertion into the left subtree of the right child of X. Single Rotation Left Left Rotation (LL Rotation) [Case 1]: Rotation does not have to be done at the root of a tree. In general, we start at the node inserted and travel up the tree, updating the balance information at every node on the path. public AVLTree rotateLeft (AVLTree x) {        AVLTree  y = x.right;        // Perform rotation            y.left = x;    ...
Read more

Disjoint Set (Union-Find)

-
A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of non-overlapping subsets. Union-Find Algorithm is an algorithm which performs two operations: Find: Determine which subset a particular element is in. Union: Join two subsets into a single subset.   Source code in java import java.util.*; import java.lang.*; import java.io.*; class Graph { int V, E; // V-> no. of vertices & E->no.of edges Edge edge[]; // /collection of all edges class Edge { int src, dest; }; // Creates a graph with V vertices and E edges Graph(int v,int e) { V = v; E = e; edge = new Edge[E]; for (int i=0; i<e; ++i) edge[i] = new Edge(); } // A utility function to find the subset of an element i int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // A uti...
Read more