- DSA 使用 Java 教程
- 使用 Java 的 DSA - 主页
- 使用 Java 的 DSA - 概述
- 使用 Java 的 DSA - 环境设置
- 使用 Java 的 DSA - 算法
- 使用 Java 的 DSA - 数据结构
- 使用 Java 的 DSA - 数组
- 使用 Java 的 DSA - 链表
- 使用 Java 的 DSA - 双向链表
- 使用 Java 的 DSA - 循环链表
- 使用Java的DSA - 堆栈内存溢出
- DSA - 解析表达式
- 使用 Java 的 DSA - 队列
- 使用 Java 的 DSA - 优先级队列
- 使用 Java 的 DSA - 树
- 使用 Java 的 DSA - 哈希表
- 使用 Java 的 DSA - 堆
- 使用 Java 的 DSA - 图
- 使用 Java 的 DSA - 搜索技术
- 使用 Java 的 DSA - 排序技术
- 使用 Java 的 DSA - 递归
- 使用 Java 的 DSA 有用资源
- 使用 Java 的 DSA - 快速指南
- 使用 Java 的 DSA - 有用资源
- 使用 Java 的 DSA - 讨论
使用 Java 的 DSA - 堆
概述
堆表示一种特殊的基于树的数据结构，用于表示优先级队列或用于堆排序。我们将具体讨论二叉堆树。
二叉堆树可以分类为具有两个约束的二叉树 -
完整性- 二叉堆树是一个完整的二叉树，除了最后一层可能没有所有元素，但应填充从左到右的元素。
堆- 所有父节点都应大于或小于其子节点。如果父节点大于其子节点，则称为最大堆，否则称为最小堆。最大堆用于堆排序，最小堆用于优先级队列。我们正在考虑最小堆并将使用数组实现。
基本操作
以下是最小堆的基本主要操作。
插入- 在堆中插入一个元素。
获取最小值- 从堆中获取最小元素。
删除最小值- 从堆中删除最小元素
插入操作
每当要插入元素时。在数组末尾插入元素。将堆大小增加 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);
}
}
}
获取最小值
获取实现堆的数组的第一个元素是根。
public int getMinimum(){
return intArray[0];
}
删除最小值
每当要删除一个元素时。获取数组的最后一个元素并将堆大小减 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);
}
}
堆实现
堆.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);
}
}
}
演示程序
堆演示.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