Dsa Using Java 简明教程
DSA using Java - Heap
Overview
堆表示一种特殊基于树的数据结构，用于表示优先级队列或堆排序。我们具体来讨论二叉堆树。
二叉堆树可以分类为具有两个约束的二叉树 −
-
Completeness − 二叉堆树是一个完全二叉树，除了最后一层可能没有所有元素，但从左到右的元素应该填充。
-
Heapness − 所有父节点都应该大于或小于它们的子节点。如果父节点大于其子节点，则称为最大堆，否则称为最小堆。最大堆用于堆排序，而最小堆用于优先级队列。我们正在考虑最小堆，并将使用数组实现相同的最小堆。
Basic Operations
以下是最小堆的基本主要操作，如下。
-
Insert − 在堆中插入一个元素。
-
Get Minimum − 从堆中获取最小元素。
-
Remove Minimum − 从堆中删除最小元素
Insert Operation
-
每当要插入一个元素时。在数组末尾插入元素。将堆的尺寸增加 1。
堆化元素，同时堆属性被破坏。比较元素与父值，并在需要时交换它们。
public void insert(int value) {
size++;
intArray[size - 1] = value;
heapUp(size - 1);
}
private void heapUp(int nodeIndex){
int parentIndex, tmp;
if (nodeIndex != 0) {
parentIndex = getParentIndex(nodeIndex);
if (intArray[parentIndex] > intArray[nodeIndex]) {
tmp = intArray[parentIndex];
intArray[parentIndex] = intArray[nodeIndex];
intArray[nodeIndex] = tmp;
heapUp(parentIndex);
}
}
}Remove Minimum
-
每当要删除一个元素时。获取数组的最后一个元素，并减少堆的尺寸 1。
堆化元素，同时堆属性被破坏。比较元素与子值，并在需要时交换它们。
public void removeMin() {
intArray[0] = intArray[size - 1];
size--;
if (size > 0)
heapDown(0);
}
private void heapDown(int nodeIndex){
int leftChildIndex, rightChildIndex, minIndex, tmp;
leftChildIndex = getLeftChildIndex(nodeIndex);
rightChildIndex = getRightChildIndex(nodeIndex);
if (rightChildIndex >= size) {
if (leftChildIndex >= size)
return;
else
minIndex = leftChildIndex;
} else {
if (intArray[leftChildIndex] <= intArray[rightChildIndex])
minIndex = leftChildIndex;
else
minIndex = rightChildIndex;
}
if (intArray[nodeIndex] > intArray[minIndex]) {
tmp = intArray[minIndex];
intArray[minIndex] = intArray[nodeIndex];
intArray[nodeIndex] = tmp;
heapDown(minIndex);
}
}Heap Implementation
Heap.java
package com.tutorialspoint.datastructure;
public class Heap {
private int[] intArray;
private int size;
public Heap(int size){
intArray = new int[size];
}
public boolean isEmpty(){
return size == 0;
}
public int getMinimum(){
return intArray[0];
}
public int getLeftChildIndex(int nodeIndex){
return 2*nodeIndex +1;
}
public int getRightChildIndex(int nodeIndex){
return 2*nodeIndex +2;
}
public int getParentIndex(int nodeIndex){
return (nodeIndex -1)/2;
}
public boolean isFull(){
return size == intArray.length;
}
public void insert(int value) {
size++;
intArray[size - 1] = value;
heapUp(size - 1);
}
public void removeMin() {
intArray[0] = intArray[size - 1];
size--;
if (size > 0)
heapDown(0);
}
/**
* Heap up the new element,until heap property is broken.
* Steps:
* 1. Compare node's value with parent's value.
* 2. Swap them, If they are in wrong order.
* */
private void heapUp(int nodeIndex){
int parentIndex, tmp;
if (nodeIndex != 0) {
parentIndex = getParentIndex(nodeIndex);
if (intArray[parentIndex] > intArray[nodeIndex]) {
tmp = intArray[parentIndex];
intArray[parentIndex] = intArray[nodeIndex];
intArray[nodeIndex] = tmp;
heapUp(parentIndex);
}
}
}
/**
* Heap down the root element being least in value,until heap property is broken.
* Steps:
* 1.If current node has no children, done.
* 2.If current node has one children and heap property is broken,
* 3.Swap the current node and child node and heap down.
* 4.If current node has one children and heap property is broken, find smaller one
* 5.Swap the current node and child node and heap down.
* */
private void heapDown(int nodeIndex){
int leftChildIndex, rightChildIndex, minIndex, tmp;
leftChildIndex = getLeftChildIndex(nodeIndex);
rightChildIndex = getRightChildIndex(nodeIndex);
if (rightChildIndex >= size) {
if (leftChildIndex >= size)
return;
else
minIndex = leftChildIndex;
} else {
if (intArray[leftChildIndex] <= intArray[rightChildIndex])
minIndex = leftChildIndex;
else
minIndex = rightChildIndex;
}
if (intArray[nodeIndex] > intArray[minIndex]) {
tmp = intArray[minIndex];
intArray[minIndex] = intArray[nodeIndex];
intArray[nodeIndex] = tmp;
heapDown(minIndex);
}
}
}Demo Program
HeapDemo.java
package com.tutorialspoint.datastructure;
public class HeapDemo {
public static void main(String[] args){
Heap heap = new Heap(10);
/* 5 //Level 0
*
*/
heap.insert(5);
/* 1 //Level 0
* |
* 5---| //Level 1
*/
heap.insert(1);
/* 1 //Level 0
* |
* 5---|---3 //Level 1
*/
heap.insert(3);
/* 1 //Level 0
* |
* 5---|---3 //Level 1
* |
* 8--| //Level 2
*/
heap.insert(8);
/* 1 //Level 0
* |
* 5---|---3 //Level 1
* |
* 8--|--9 //Level 2
*/
heap.insert(9);
/* 1 //Level 0
* |
* 5---|---3 //Level 1
* | |
* 8--|--9 6--| //Level 2
*/
heap.insert(6);
/* 1 //Level 0
* |
* 5---|---2 //Level 1
* | |
* 8--|--9 6--|--3 //Level 2
*/
heap.insert(2);
System.out.println(heap.getMinimum());
heap.removeMin();
/* 2 //Level 0
* |
* 5---|---3 //Level 1
* | |
* 8--|--9 6--| //Level 2
*/
System.out.println(heap.getMinimum());
}
}如果我们编译并运行上述程序，它将生成以下结果 -
1
2