[JAVA] Binary tree memorandum for beginners (Part 4 Binary heap)

Part 3 is here

Binary heap

So far, I have explained the outline of the binary tree. From this time, I will explain a concrete example of a binary tree. The first example is a binary tree called a binary heap. The structure is simple, it's just a complete binary tree whose parent data is always smaller than the child data. A complete binary tree was a binary tree with no vacancy at the nodes that were not leaves, and all the leaves were left-justified. Since the binary heap is a kind of complete binary tree, it can be realized by using an array.

Implementation example

C++

BinaryHeap.cpp


#include <iostream>
using namespace std;

void breadthFirstSearch(int binaryTree[], int nodeNum);
int insertNode(int binaryHeap[], int value, int nodeNum);
int deleteNode(int binaryHeap[], int value, int nodeNum);
int searchNode(int binaryHeap[], int value, int nodeNum, int index);

//Function to display in the order of breadth-first search
void breadthFirstSearch(int binaryTree[], int nodeNum)
{
	for (int i = 0; i < nodeNum; i++) {
		cout << binaryTree[i] << " ";
	}
	cout << endl;
}

//A function that inserts a new node into the binary heap
//Returns 1 on success, 0 on failure
int insertNode(int binaryHeap[], int value, int nodeNum)
{
	//Do nothing if there is already value
	if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
		return 0;
	}
	//Temporarily inserted at the end
	binaryHeap[nodeNum] = value;
	int i = nodeNum;

	//Follow from the tail to the root
	while (i > 0) {
		//If the parent is bigger
		if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
			//Exchange parents and children
			binaryHeap[i] = binaryHeap[(i - 1) / 2];
			binaryHeap[(i - 1) / 2] = value;
			i = (i - 1) / 2;
		}
		//If the parent is smaller
		else {
			return 1;
		}
	}

	return 1;
}

//A function that removes nodes with value in the data from the binary heap
//Returns 1 on success, 0 on failure
int deleteNode(int binaryHeap[], int value, int nodeNum)
{
	int index = searchNode(binaryHeap, value, nodeNum, 0);
	//Do nothing if there is no value in the binaryHeap
	if (index == -1) {
		return 0;
	}

	//Temporarily move the last data
	binaryHeap[index] = binaryHeap[nodeNum - 1];
	// binaryHeap[index]Loop as long as there are children
	//Note that the total number of nodes has been reduced by one.
	while (2 * index + 1 < nodeNum - 1) {
		int childIndex, childValue;

		//If there is only the left child
		if (2 * index + 1 == nodeNum - 2) {
			childIndex = 2 * index + 1;
			childValue = binaryHeap[2 * index + 1];
		}
		//If you have left and right children
		else {
			//If the child on the left is smaller
			if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
				childIndex = 2 * index + 1;
				childValue = binaryHeap[2 * index + 1];
			}
			//If the right child is smaller
			else {
				childIndex = 2 * index + 2;
				childValue = binaryHeap[2 * index + 2];
			}
		}

		//Compare your current position with the smaller child
		//If the current position is larger
		if	(binaryHeap[index]	>	childValue)	{
			//Swap the current position and child
			binaryHeap[childIndex]	=	binaryHeap[index];
			binaryHeap[index]	=	childValue;
			index	=	childIndex;
		}
		//If the child is larger
		else	{
			return	1;
		}
	}

	return	1;
}

//A function that searches the binary heap for nodes that have value in the data
//Index of the node if successful, if unsuccessful-Returns 1
int	searchNode(int binaryHeap[], int value, int nodeNum, int index)
{
	//Do nothing if the number of nodes is 0
	if (nodeNum == 0) {
		return -1;
	}

	//Scan in the order of destination
	//Successful search
	if (binaryHeap[index] == value) {
		return index;
	}

	//Search failure
	else if (binaryHeap[index] > value) {
		return -1;
	}

	//Still continue
	else {
		int leftResult = -1, rightResult = -1;
		if (2 * index + 1 < nodeNum) {
			leftResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 1);
		}
		if (2 * index + 2 < nodeNum) {
			rightResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 2);
		}

		if (leftResult == -1 && rightResult == -1) {
			return -1;
		}
		else if (leftResult != -1) {
			return leftResult;
		}
		else {
			return rightResult;
		}
	}
}

int main()
{
	int binaryHeap[100];
	int nodeNum = 0;

	nodeNum += insertNode(binaryHeap, 8, nodeNum);
	nodeNum += insertNode(binaryHeap, 12, nodeNum);
	nodeNum += insertNode(binaryHeap, 19, nodeNum);
	nodeNum += insertNode(binaryHeap, 9, nodeNum);
	nodeNum += insertNode(binaryHeap, 4, nodeNum);
	nodeNum += insertNode(binaryHeap, 21, nodeNum);
	nodeNum += insertNode(binaryHeap, 2, nodeNum);
	nodeNum += insertNode(binaryHeap, 14, nodeNum);

	//Do not allow duplicate insertion
	nodeNum += insertNode(binaryHeap, 14, nodeNum);
	breadthFirstSearch(binaryHeap, nodeNum);
	cout << "nodeNum: " << nodeNum << endl;

	int index = searchNode(binaryHeap, 14, nodeNum, 0);
	cout << "index: " << index << ", value: " << binaryHeap[14] << endl;

	//If you look for a node that does not exist-1 is back
	index = searchNode(binaryHeap, 1, nodeNum, 0);
	cout << "index: " << index << endl;

	nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
	nodeNum -= deleteNode(binaryHeap, 2, nodeNum);
	nodeNum -= deleteNode(binaryHeap, 21, nodeNum);

	//You can't delete what you don't have
	nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
	breadthFirstSearch(binaryHeap, nodeNum);
	cout << "nodeNum: " << nodeNum << endl;
}

Java

BinaryHeap.java


public class BinaryHeapAnswer {
	//Function to display in the order of breadth-first search
	public static void breadthFirstSearch(int[] binaryTree, int nodeNum) {
		for (int i = 0; i < nodeNum; i++) {
			System.out.print(binaryTree[i] + " ");
		}
		System.out.println("");
	}

	//A function that inserts a new node into the binary heap
	//Returns 1 on success, 0 on failure
	public static int insertNode(int[] binaryHeap, int value, int nodeNum) {
		//Do nothing if there is already value
		if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
			return 0;
		}
		//Temporarily inserted at the end
		binaryHeap[nodeNum] = value;
		int i = nodeNum;

		//Follow from the tail to the root
		while (i > 0) {
			//If the parent is bigger
			if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
				//Exchange parents and children
				binaryHeap[i] = binaryHeap[(i - 1) / 2];
				binaryHeap[(i - 1) / 2] = value;
				i = (i - 1) / 2;
			}
			//If the parent is smaller
			else {
				return 1;
			}
		}

		return 1;
	}

	//A function that removes nodes with value in the data from the binary heap
	//Returns 1 on success, 0 on failure
	public static int deleteNode(int[] binaryHeap, int value, int nodeNum) {
		int index = searchNode(binaryHeap, value, nodeNum, 0);
		//Do nothing if there is no value in the binaryHeap
		if (index == -1) {
			return 0;
		}

		//Temporarily move the last data
		binaryHeap[index] = binaryHeap[nodeNum - 1];
		// binaryHeap[index]Loop as long as there are children
		//Note that the total number of nodes has been reduced by one.
		while (2 * index + 1 < nodeNum - 1) {
			int childIndex, childValue;

			//If there is only the left child
			if (2 * index + 1 == nodeNum - 2) {
				childIndex = 2 * index + 1;
				childValue = binaryHeap[2 * index + 1];
			}
			//If you have left and right children
			else {
				//If the child on the left is smaller
				if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
					childIndex = 2 * index + 1;
					childValue = binaryHeap[2 * index + 1];
				}
				//If the right child is smaller
				else {
					childIndex = 2 * index + 2;
					childValue = binaryHeap[2 * index + 2];
				}
			}

			//Compare your current position with the smaller child
			//If the current position is larger
			if (binaryHeap[index] > childValue) {
				//Swap the current position and child
				binaryHeap[childIndex] = binaryHeap[index];
				binaryHeap[index] = childValue;
				index = childIndex;
			}
			//If the child is larger
			else {
				return 1;
			}
		}

		return 1;
	}

	//A function that searches the binary heap for nodes that have value in the data
	//Index of the node if successful, if unsuccessful-Returns 1
	public static int searchNode(int[] binaryHeap, int value, int nodeNum, int index) {
		//Do nothing if the number of nodes is 0
		if (nodeNum == 0) {
			return -1;
		}

		//Scan in the order of destination
		//Successful search
		if (binaryHeap[index] == value) {
			return index;
		}

		//Search failure
		else if (binaryHeap[index] > value) {
			return -1;
		}

		//Still continue
		else {
			int leftResult = -1, rightResult = -1;
			if (2 * index + 1 < nodeNum) {
				leftResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 1);
			}
			if (2 * index + 2 < nodeNum) {
				rightResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 2);
			}

			if (leftResult == -1 && rightResult == -1) {
				return -1;
			}
			else if (leftResult != -1) {
				return leftResult;
			}
			else {
				return rightResult;
			}
		}
	}

	public static void main(String[] args) {
		int[] binaryHeap = new int[100];
		int nodeNum = 0;

		nodeNum += insertNode(binaryHeap, 8, nodeNum);
		nodeNum += insertNode(binaryHeap, 12, nodeNum);
		nodeNum += insertNode(binaryHeap, 19, nodeNum);
		nodeNum += insertNode(binaryHeap, 9, nodeNum);
		nodeNum += insertNode(binaryHeap, 4, nodeNum);
		nodeNum += insertNode(binaryHeap, 21, nodeNum);
		nodeNum += insertNode(binaryHeap, 2, nodeNum);
		nodeNum += insertNode(binaryHeap, 14, nodeNum);

		//Do not allow duplicate insertion
		nodeNum += insertNode(binaryHeap, 14, nodeNum);
		breadthFirstSearch(binaryHeap, nodeNum);
		System.out.println("nodeNum: " + nodeNum);

		int index = searchNode(binaryHeap, 14, nodeNum, 0);
		System.out.println("index: " + index + ", value: " + binaryHeap[14]);

		//If you look for a node that does not exist-1 is back
		index = searchNode(binaryHeap, 1, nodeNum, 0);
		System.out.println("index: " + index);

		nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
		nodeNum -= deleteNode(binaryHeap, 2, nodeNum);
		nodeNum -= deleteNode(binaryHeap, 21, nodeNum);

		//You can't delete what you don't have
		nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
		breadthFirstSearch(binaryHeap, nodeNum);
		System.out.println("nodeNum: " + nodeNum);
	}
}

The execution result is as follows.

2 8 4 12 9 21 19 14
nodeNum: 8
index: 7, value: 0
index: -1
4 8 19 12 9
nodeNum: 5

Explanation about implementation

The following functions are implemented in the above program.

--void breadthFirstSearch (int [] binaryTree, int nodeNum): A function that displays a binary tree in the order of breadth-first search. --int insertNode (int [] binaryHeap, int value, int nodeNum): A function that inserts a new node with value as data into the binary heap. --int searchNode (int [] binaryHeap, int value, int nodeNum): A function that searches the binary heap for nodes that have value as data. --int deleteNode (int [] binaryHeap, int value, int nodeNum): A function that deletes a node having value as data from the binary heap.

The searchNode function scans in the order of destination. In the binary heap, the child data is always larger than the parent data, so I try to return when the current node data is larger than the value.

In the insertNode function, first, the searchNode function is used to check whether there is a node in the binary heap that has value as data. If it already exists, it will return without creating a new node. If not, first add a node at the end of the array. Then compare the size with the parent for that position and, if the parent is larger, exchange itself with the parent. Repeat the previous operation until the current position becomes the root or the parent becomes smaller, and the insertion is completed.

Lastly, regarding the deleteNode function, I will explain the procedure for comparing nodes, which is a bottleneck when considering the operation of this function. First, compare which of the left and right children is smaller and remember the smaller one. If there is only the left child, remember the left child. By the way, since the binary heap is a complete binary tree, it is impossible to have only the right child. Next, compare which of the memorized child and the node at the current position is smaller. If the child is larger, it cannot move any further and will end the comparison. If the current position is larger, it will be replaced with the child, and that will be used as the current position to compare with the child again. Repeat this comparison, and if the current position is a leaf, end there.

Now, regarding the operation of the deleteNode function, first, use the searchNode function to get the index of the target node. Then move the last node to that position. All you have to do now is compare the node with the child and move it until it fits in the proper position.

It may have been a little difficult, but I hope you can understand the binary heap somehow. Next time, I will explain about binary search trees.

Part 5 is here

Recommended Posts

Binary tree memorandum for beginners (Part 4 Binary heap)
Binary Tree Memorandum for Beginners (Part 1)
Binary tree memorandum for beginners (Part 5 Binary search tree)
Binary tree memorandum for beginners (Part 2 Search for binary trees)
Binary tree memorandum for beginners (Part 3 Realization using class)
A memorandum for android application development beginners
CI / CD practice for beginners --Part2 --CI / CD tool construction
CI / CD practice for beginners --Part1 --Environment construction
CI / CD practice for beginners --Part3 --Preparation for development project
Scraping for beginners (Ruby)
Tutorial to create a blog with Rails for beginners Part 1
Tutorial to create a blog with Rails for beginners Part 2
Tutorial to create a blog with Rails for beginners Part 0