What’s the relationship between “a” heap and “the” heap?
A Heap:
“A Heap” refers to the heap data structure where we can store data in a specific order. Heap is a Tree-based data structure where the tree is a complete binary tree.
Heap is basically of two types:
- Max-Heap: The key at the Root node of the tree will be the greatest among all the keys present in that heap and the same property will be followed by every sub-tree.
- Min-Heap: The key at the Root node of the tree will be the smallest among all the keys present in that heap and the same property will be followed by every sub-tree.
Implementation:
Below is the implementation of the Max-Heap Data Structure
#include <bits/stdc++.h>
using namespace std;
#define N 100
// Heap Structure..
class Heap {
int heap[N];
int heapsize = -1;
void Heapifyup()
{
int i = heapsize;
while (i >= 0) {
if (heap[i] <= heap[(i - 1) / 2]) {
break;
}
else {
swap(heap[i], heap[(i - 1) / 2]);
}
i = (i - 1) / 2;
}
}
void Heapifydown()
{
int i = 0;
while (i != heapsize) {
if (heap[i]
>= max(heap[2 * i + 1], heap[2 * i + 2])) {
break;
}
else {
int k;
k = (heap[2 * i + 1] >= heap[2 * i + 2])
? 2 * i + 1
: 2 * i + 2;
swap(heap[i], heap[k]);
i = k;
}
}
}
public:
void push(int val)
{
heapsize++;
heap[heapsize] = val;
Heapifyup();
// heapify bottom up
}
void pop()
{
if (heapsize < 0) {
cout << "Heap Underflow \n";
return;
}
heap[0] = heap[heapsize];
heapsize--;
if (heapsize > 0) {
Heapifydown();
// heapify top down
}
}
void print_heap()
{
for (int i = 0; i <= heapsize; i++) {
cout << heap[i] << " ";
}
cout << endl;
}
int size() { return heapsize + 1; }
int top()
{
if (heapsize < 0) {
return -1;
}
return heap[0];
}
};
// Driver code
int main(int argc, char const* argv[])
{
Heap h;
cout << h.top() << endl;
cout << h.size() << endl;
h.print_heap();
h.pop();
h.push(5);
h.push(7);
cout << h.top() << endl;
h.push(6);
h.push(4);
h.print_heap();
cout << h.size() << endl;
h.pop();
h.print_heap();
cout << h.size() << endl;
return 0;
}
// Java Code for the above approach
import java.io.*;
// Heap Structure..
class Heap {
int[] heap = new int[100];
int heapsize = -1;
void Heapifyup()
{
int i = heapsize;
while (i >= 0) {
if (heap[i] <= heap[(i - 1) / 2]) {
break;
}
else {
int temp = heap[i];
heap[i] = heap[(i - 1) / 2];
heap[(i - 1) / 2] = temp;
}
i = (i - 1) / 2;
}
}
void Heapifydown()
{
int i = 0;
while (i != heapsize) {
if (heap[i] >= Math.max(heap[2 * i + 1],
heap[2 * i + 2])) {
break;
}
else {
int k;
k = (heap[2 * i + 1] >= heap[2 * i + 2]
? 2 * i + 1
: 2 * i + 2);
int temp = heap[i];
heap[i] = heap[k];
heap[k] = temp;
i = k;
}
}
}
void push(int val)
{
heapsize++;
heap[heapsize] = val;
Heapifyup();
// heapify bottom up
}
void pop()
{
if (heapsize < 0) {
System.out.println("Heap Underflow ");
return;
}
heap[0] = heap[heapsize];
heapsize--;
if (heapsize > 0) {
Heapifydown();
// heapify top down
}
}
void print_heap()
{
for (int i = 0; i <= heapsize; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
int size() { return heapsize + 1; }
int top()
{
if (heapsize < 0) {
return -1;
}
return heap[0];
}
}
class GFG {
public static void main(String[] args)
{
Heap h = new Heap();
System.out.println(h.top());
System.out.println(h.size());
h.print_heap();
h.pop();
h.push(5);
h.push(7);
System.out.println(h.top());
h.push(6);
h.push(4);
h.print_heap();
System.out.println(h.size());
h.pop();
h.print_heap();
System.out.println(h.size());
}
}
// This code is contributed by lokeshmvs21.
// C# code for the above approach
using System;
class Heap {
private int[] heap = new int[100];
private int heapsize = -1;
// Heapify up function
private void Heapifyup()
{
int i = heapsize;
while (i >= 0) {
if (heap[i] <= heap[(i - 1) / 2]) {
break;
}
else {
int temp = heap[i];
heap[i] = heap[(i - 1) / 2];
heap[(i - 1) / 2] = temp;
}
i = (i - 1) / 2;
}
}
// Heapify down function
private void Heapifydown()
{
int i = 0;
while (i != heapsize) {
if (heap[i] >= Math.Max(heap[2 * i + 1],
heap[2 * i + 2])) {
break;
}
else {
int k;
k = (heap[2 * i + 1] >= heap[2 * i + 2]
? 2 * i + 1
: 2 * i + 2);
int temp = heap[i];
heap[i] = heap[k];
heap[k] = temp;
i = k;
}
}
}
// Push function to insert a value into the heap
public void push(int val)
{
heapsize++;
heap[heapsize] = val;
Heapifyup();
}
// Pop function to remove the root element from the heap
public void pop()
{
if (heapsize < 0) {
Console.WriteLine("Heap Underflow");
return;
}
heap[0] = heap[heapsize];
heapsize--;
if (heapsize > 0) {
Heapifydown();
}
}
// Print_heap function to print the elements in the heap
public void print_heap()
{
for (int i = 0; i <= heapsize; i++) {
Console.Write(heap[i] + " ");
}
Console.WriteLine();
}
// Size function to return the size of the heap
public int size() { return heapsize + 1; }
// Top function to return the root element of the heap
public int top()
{
if (heapsize < 0) {
return -1;
}
return heap[0];
}
}
class GFG {
// Driver code
static void Main(string[] args)
{
Heap h = new Heap();
Console.WriteLine(h.top());
Console.WriteLine(h.size());
h.print_heap();
h.pop();
h.push(5);
h.push(7);
Console.WriteLine(h.top());
h.push(6);
h.push(4);
h.print_heap();
Console.WriteLine(h.size());
h.pop();
h.print_heap();
Console.WriteLine(h.size());
}
}
// This code is contributed by phasing17.
// javascript code implementation
const N = 100;
// Heap Structure..
class Heap {
constructor(){
this.heap = new Array(N).fill(0);
this.heapsize = -1;
}
Heapifyup()
{
let i = this.heapsize;
let j;
while (i >= 0) {
let x = Math.floor((i == 0) ? 0:(i-1)/2);
if (this.heap[i] <= this.heap[x]) {
break;
}
else {
// swapping heap[i], heap[j]
let temp = this.heap[i];
this.heap[i] = this.heap[x];
this.heap[(i == 0)? 0:(i-1)/2] = temp;
}
i = Math.floor(i == 0 ? 0: (i-1)/2);
}
}
Heapifydown()
{
let i = 0;
while (i != this.heapsize) {
if (this.heap[i] >= Math.max(this.heap[2 * i + 1], this.heap[2 * i + 2])) {
break;
}
else {
let k = (this.heap[2 * i + 1] >= this.heap[2 * i + 2]) ? 2 * i + 1 : 2 * i + 2;
// swapping heap[i] and heap[k]
let temp = this.heap[i];
this.heap[i] = this.heap[k];
this.heap[k] = temp;
i = k;
}
}
}
push(val)
{
this.heapsize = this.heapsize + 1;
this.heap[this.heapsize] = val;
this.Heapifyup();
}
pop()
{
if (this.heapsize < 0) {
console.log("Heap Underflow");
return;
}
this.heap[0] = this.heap[this.heapsize];
this.heapsize = this.heapsize - 1;
if (this.heapsize > 0) {
this.Heapifydown();
// heapify top down
}
}
print_heap()
{
for (let i = 0; i <= this.heapsize; i++) {
process.stdout.write(this.heap[i] + " ");
}
console.log()
}
size(){
return this.heapsize + 1;
}
top()
{
// console.log(this.heap);
if (this.heapsize < 0) {
return -1;
}
return this.heap[0];
}
};
// Driver code
let h = new Heap();
console.log(h.top());
console.log(h.size());
h.print_heap();
h.pop();
h.push(5);
h.push(7);
console.log(h.top());
h.push(6);
h.push(4);
h.print_heap();
console.log(h.size());
h.pop();
h.print_heap();
console.log(h.size());
// The code is contributed by Nidhi goel.
# Python3 code implementation
N = 100
# Heap Structure
class Heap:
def __init__(self):
# Initializing the heap
self.heap = [0] * N
self.heapsize = -1
# Heapifyup function to adjust the heap after pushing elements
def Heapifyup(self):
i = self.heapsize
while i >= 0:
x = (i - 1) // 2 if i != 0 else 0
# If the child node is greater than parent node, swap them
if self.heap[i] <= self.heap[x]:
break
else:
# swapping heap[i], heap[j]
temp = self.heap[i]
self.heap[i] = self.heap[x]
self.heap[x] = temp
i = (i - 1) // 2
# Heapifydown function to adjust the heap after popping elements
def Heapifydown(self):
i = 0
while i != self.heapsize:
# Get the index of the largest child
k = 2 * i + 1 if self.heap[2 * i + 1] >= self.heap[2 * i + 2] else 2 * i + 2
# If the parent node is greater than its largest child, break
if self.heap[i] >= self.heap[k]:
break
else:
# swapping heap[i] and heap[k]
temp = self.heap[i]
self.heap[i] = self.heap[k]
self.heap[k] = temp
i = k
# Push function to insert elements into the heap
def push(self, val):
self.heapsize += 1
self.heap[self.heapsize] = val
self.Heapifyup()
# Pop function to remove the largest element from the heap
def pop(self):
if self.heapsize < 0:
print("Heap Underflow")
return
self.heap[0] = self.heap[self.heapsize]
self.heapsize -= 1
if self.heapsize > 0:
self.Heapifydown()
# Function to print the heap
def print_heap(self):
for i in range(self.heapsize + 1):
print(self.heap[i], end=" ")
print()
# Size function to return the size of the heap
def size(self):
return self.heapsize + 1
# Top function to return the largest element of the heap
def top(self):
if self.heapsize < 0:
return -1
return self.heap[0]
# Driver code
h = Heap()
print(h.top()) # prints -1
print(h.size()) # prints 0
h.print_heap() # prints nothing
h.pop() # Heap underflow
h.push(5)
h.push(7)
print(h.top()) # prints 7
h.push(6)
h.push(4)
h.print_heap() # prints 7 5 6 4
print(h.size()) # prints 4
h.pop()
h.print_heap() # prints 6 5 4
print(h.size()) # prints 3
# The code is contributed by phasing17
Output
-1 0 Heap Underflow 7 7 5 6 4 4 6 5 4 3
Below is the implementation of the Min-Heap Data Structure
#include <bits/stdc++.h>
using namespace std;
#define N 100
// Heap Structure..
class Heap {
int heap[N];
int heapsize = -1;
void Heapifyup()
{
int i = heapsize;
while (i >= 0) {
if (heap[i] >= heap[(i - 1) / 2]) {
break;
}
else {
swap(heap[i], heap[(i - 1) / 2]);
}
i = (i - 1) / 2;
}
}
void Heapifydown()
{
int i = 0;
while (i != heapsize) {
if (heap[i]
<= min(heap[2 * i + 1], heap[2 * i + 2])) {
break;
}
else {
int k;
k = (heap[2 * i + 1] <= heap[2 * i + 2])
? 2 * i + 1
: 2 * i + 2;
swap(heap[i], heap[k]);
i = k;
}
}
}
public:
void push(int val)
{
heapsize++;
heap[heapsize] = val;
Heapifyup();
// heapify bottom up
}
void pop()
{
if (heapsize < 0) {
cout << "Heap Underflow \n";
return;
}
heap[0] = heap[heapsize];
heapsize--;
if (heapsize > 0) {
Heapifydown();
// heapify top down
}
}
void print_heap()
{
for (int i = 0; i <= heapsize; i++) {
cout << heap[i] << " ";
}
cout << endl;
}
int size() { return heapsize + 1; }
int top()
{
if (heapsize < 0) {
return -1;
}
return heap[0];
}
};
int main(int argc, char const* argv[])
{
Heap h;
cout << h.top() << endl;
cout << h.size() << endl;
h.print_heap();
h.pop();
h.push(5);
h.push(7);
cout << h.top() << endl;
h.push(6);
h.push(4);
h.print_heap();
cout << h.size() << endl;
h.pop();
h.print_heap();
cout << h.size() << endl;
return 0;
}
public class Heap {
private int[] heap;
private int heapsize;
public Heap() {
heap = new int[100]; // Same as N in C++
heapsize = -1;
}
private void heapifyUp() {
int i = heapsize;
while (i >= 0) {
if (heap[i] >= heap[(i - 1) / 2]) {
break;
} else {
swap(i, (i - 1) / 2);
}
i = (i - 1) / 2;
}
}
private void heapifyDown() {
int i = 0;
while (2 * i + 1 <= heapsize) { // Check if left child exists
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
int smallest = i;
if (heap[leftChild] < heap[smallest]) {
smallest = leftChild;
}
if (rightChild <= heapsize && heap[rightChild] < heap[smallest]) { // Check if right child exists
smallest = rightChild;
}
if (smallest == i) {
break;
}
swap(i, smallest);
i = smallest;
}
}
public void push(int val) {
heapsize++;
heap[heapsize] = val;
heapifyUp();
}
public void pop() {
if (heapsize < 0) {
System.out.println("Heap Underflow");
return;
}
heap[0] = heap[heapsize];
heapsize--;
if (heapsize > 0) {
heapifyDown();
}
}
public void printHeap() {
for (int i = 0; i <= heapsize; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
public int size() {
return heapsize + 1;
}
public int top() {
if (heapsize < 0) {
return -1;
}
return heap[0];
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public static void main(String[] args) {
Heap h = new Heap();
System.out.println(h.top());
System.out.println(h.size());
h.printHeap();
h.pop();
h.push(5);
h.push(7);
System.out.println(h.top());
h.push(6);
h.push(4);
h.printHeap();
System.out.println(h.size());
h.pop();
h.printHeap();
System.out.println(h.size());
}
}
using System;
class Heap {
private int[] heap = new int[100]; // Heap array
private int heapSize = -1; // Initial heap size
// Method to maintain the heap property while inserting an element
private void HeapifyUp() {
int i = heapSize;
while (i >= 0) {
if (heap[i] >= heap[(i - 1) / 2]) {
break;
}
else {
Swap(ref heap[i], ref heap[(i - 1) / 2]);
}
i = (i - 1) / 2;
}
}
// Method to maintain the heap property while removing an element
private void HeapifyDown() {
int i = 0;
while (i <= heapSize) {
int leftChildIndex = 2 * i + 1;
int rightChildIndex = 2 * i + 2;
// Check if left child exists
if (leftChildIndex <= heapSize) {
int minValueChildIndex = leftChildIndex;
// Check if right child exists and is smaller than left child
if (rightChildIndex <= heapSize && heap[rightChildIndex] < heap[leftChildIndex]) {
minValueChildIndex = rightChildIndex;
}
// Compare the current node with the minimum value child
if (heap[i] <= heap[minValueChildIndex]) {
break; // Heap property satisfied
}
else {
Swap(ref heap[i], ref heap[minValueChildIndex]);
i = minValueChildIndex;
}
}
else {
break; // No child nodes
}
}
}
// Method to insert an element into the heap
public void Push(int val) {
heapSize++;
heap[heapSize] = val;
HeapifyUp();
}
// Method to remove the root element from the heap
public void Pop() {
if (heapSize < 0) {
Console.WriteLine("Heap Underflow");
return;
}
heap[0] = heap[heapSize];
heapSize--;
if (heapSize > 0) {
HeapifyDown();
}
}
// Method to print the heap
public void PrintHeap() {
for (int i = 0; i <= heapSize; i++) {
Console.Write(heap[i] + " ");
}
Console.WriteLine();
}
// Method to get the size of the heap
public int Size() {
return heapSize + 1;
}
// Method to get the root element of the heap
public int Top() {
if (heapSize < 0) {
return -1;
}
return heap[0];
}
// Method to swap two elements
private void Swap(ref int a, ref int b) {
int temp = a;
a = b;
b = temp;
}
}
class MainClass {
public static void Main(string[] args) {
Heap h = new Heap();
Console.WriteLine(h.Top()); // Print top element (should be -1)
Console.WriteLine(h.Size()); // Print size of heap (should be 0)
h.PrintHeap(); // Print heap
h.Pop(); // Pop an element
h.Push(5); // Push elements into the heap
h.Push(7);
Console.WriteLine(h.Top()); // Print top element (should be 5)
h.Push(6);
h.Push(4);
h.PrintHeap(); // Print heap
Console.WriteLine(h.Size()); // Print size of heap
h.Pop(); // Pop an element
h.PrintHeap(); // Print heap
Console.WriteLine(h.Size()); // Print size of heap
}
}
//This code is contributed by Monu.
class Heap {
constructor() {
// Initialize an empty array to store the elements of the heap
this.heap = [];
}
// Method to add an element to the heap
push(val) {
// Add the new value to the end of the array
this.heap.push(val);
// Restore the heap property by moving the newly added element up
this.heapifyUp(this.heap.length - 1);
}
// Method to remove the root element from the heap
pop() {
// Check for heap underflow
if (this.heap.length === 0) {
console.log("Heap Underflow");
return;
}
// Replace the root with the last element and remove the last element
this.heap[0] = this.heap.pop();
// Restore the heap property by moving the root element down
this.heapifyDown(0);
}
// Method to print the elements of the heap
printHeap() {
console.log(this.heap);
}
// Method to return the number of elements in the heap
size() {
return this.heap.length;
}
// Method to return the value of the root element (minimum value in a min-heap)
top() {
if (this.heap.length === 0) {
return -1; // Return -1 if the heap is empty
}
return this.heap[0];
}
// Method to restore the heap property by moving an element up
heapifyUp(index) {
let parent;
while (index > 0) {
parent = Math.floor((index - 1) / 2); // Calculate the index of the parent
if (this.heap[parent] <= this.heap[index]) {
break; // If the parent is smaller than or equal to the current element, stop
}
// Swap the current element with its parent
[this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
index = parent; // Update the index to the parent index for the next iteration
}
}
// Method to restore the heap property by moving an element down
heapifyDown(index) {
let left, right, smallest;
while (true) {
left = 2 * index + 1; // Calculate the index of the left child
right = 2 * index + 2; // Calculate the index of the right child
smallest = index;
// Check if the left child exists and is smaller than the current smallest
if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
// Check if the right child exists and is smaller than the current smallest
if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
// If the smallest element is already the current element, stop
if (smallest === index) {
break;
}
// Swap the current element with the smallest child
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest; // Update the index to the smallest child index for the next iteration
}
}
}
// Testing the Heap class
let h = new Heap();
console.log(h.top());
console.log(h.size());
h.printHeap();
h.pop();
h.push(5);
h.push(7);
console.log(h.top());
h.push(6);
h.push(4);
h.printHeap();
console.log(h.size());
h.pop();
h.printHeap();
console.log(h.size());
import heapq
class Heap:
def __init__(self):
self.heap = []
def push(self, val):
heapq.heappush(self.heap, val)
def pop(self):
if not self.heap:
print("Heap Underflow")
return
heapq.heappop(self.heap)
def print_heap(self):
print(self.heap)
def size(self):
return len(self.heap)
def top(self):
if not self.heap:
return -1
return self.heap[0]
# Driver Code
if __name__ == '__main__':
h = Heap()
print(h.top())
print(h.size())
h.print_heap()
h.pop()
h.push(5)
h.push(7)
print(h.top())
h.push(6)
h.push(4)
h.print_heap()
print(h.size())
h.pop()
h.print_heap()
print(h.size())
Output
-1 0 Heap Underflow 5 4 5 6 7 4 5 7 6 3
The Heap:
“The Heap” refers to the dynamic memory as an alternative to the local stack memory. Local memory is quite automatic. Local variables are allocated automatically when a function is called, and they are deallocated automatically when the function exits. Heap memory is different in every way.
Advantages of Using Heap Memory:
- It allows us to access variables globally.
- Does not have a specific limit on memory size.
- Variables can be resized in any instance.
- Memory allocated by the heap is not contiguous rather is allocated in any random order.
Disadvantages of Using Heap Memory:
- Heap space is not used as efficiently. Memory can become fragmented as blocks of memory are first allocated and then freed.
- Slower execution compared to stack
- Allocation is manually done by the programmers so explicit de-allocation is needed.
Below is the implementation of using Heap Memory:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int* arr = new int[5]; // initializing array using heap memory
// arr= {0, 1, 2, 3, 4}
for (int i = 0; i < 5; i++) {
arr[i] = i;
}
cout << *arr << endl; // pointer always points to first element of an array the first element
cout << *(arr + 1) << endl;
return 0;
}
import java.util.Arrays;
public class Main {
public static void main(String[] args)
{
int[] arr = new int[5]; // initializing array using stack memory
// arr = {0, 1, 2, 3, 4}
for (int i = 0; i < 5; i++) {
arr[i] = i;
}
System.out.println(arr[0]); // the first element of the array
System.out.println(arr[1]);
}
}
using System;
public class MainClass {
public static void Main(string[] args)
{
int[] arr = new int[5]; // initializing array using stack memory
// arr = {0, 1, 2, 3, 4}
for (int i = 0; i < 5; i++) {
arr[i] = i;
}
Console.WriteLine(arr[0]); // the first element of the array
Console.WriteLine(arr[1]);
}
}
// Initialize array using stack memory
let arr = new Array(5);
// Fill the array with values from 0 to 4
for (let i = 0; i < 5; i++) {
arr[i] = i;
}
// Print the first element of the array
console.log(arr[0]);
// Print the second element of the array
console.log(arr[1]);
# Python code for the above approach
# Initializing a list using dynamic memory allocation (similar to heap memory in C++)
arr = []
for i in range(5):
arr.append(i)
# Accessing elements in the list using indices
# Printing the value stored at the first index
print(arr[0])
# Printing the value stored at the second index
print(arr[1])
Output
0 1
Time Complexity: O(1)
Auxiliary Space: O(1)
Related Articles:
Contact Us