英文:
Min Heap implementation using Arrays in java
问题
试图使用数组实现最小堆。我遇到的问题是当我从堆中轮询一个元素时，从技术上讲，它应该返回堆中的最小元素。但是使用我编写的代码时，它并没有给出最小的元素。
输出：
插入堆：1 3 2 6 4 5
轮询值：1
轮询后的新堆：3 5 2 6 4
轮询值：3
轮询后的新堆：4 5 2 6
轮询值：4
轮询后的新堆：5 6 2
期望输出：
在轮询时应该返回最小值
主类代码：
public class HeapApp {
public static void main(String[] args) {
Heap hg = new Heap(6);
hg.insert(6);
hg.insert(5);
hg.insert(4);
hg.insert(3);
hg.insert(2);
hg.insert(1);
System.out.print("插入堆：");
hg.print();
System.out.println();
System.out.println("轮询值：" + hg.poll());
System.out.print("轮询后的新堆：");
hg.print();
System.out.println();
System.out.println("轮询值：" + hg.poll());
System.out.print("轮询后的新堆：");
hg.print();
System.out.println();
System.out.println("轮询值：" + hg.poll());
System.out.print("轮询后的新堆：");
hg.print();
}
}
堆类：
public class Heap {
private int heapSize;
private int arr[];
Heap(int capacity) {
heapSize = 0;
arr = new int[capacity];
}
public boolean isFull() {
return heapSize == arr.length;
}
public boolean isEmpty() {
return heapSize == 0;
}
public void insert(int element) {
if (isFull()) {
throw new RuntimeException("堆已满");
}
arr[heapSize] = element;
heapSize++;
heapifyUp();
}
private void heapifyUp() {
int index = heapSize - 1;
while (index > 0) {
if (arr[(index - 1) / 2] > arr[index]) {
int temp = arr[index];
arr[index] = arr[(index - 1) / 2];
arr[(index - 1) / 2] = temp;
index = (index - 1) / 2;
} else {
break;
}
}
}
public int poll() {
if (isEmpty())
throw new RuntimeException("堆为空");
int ans = arr[0];
arr[0] = arr[heapSize - 1];
heapSize--;
heapifyDown();
return ans;
}
private void heapifyDown() {
int index = 0;
int left = 2 * index + 1;
while (left < heapSize) {
int min = left;
int right = ++left;
if (right < heapSize) {
if (arr[left] > arr[right]) {
min++;
}
}
if (arr[index] > arr[min]) {
int temp = arr[min];
arr[min] = arr[index];
arr[index] = temp;
}
index = min;
left = 2 * index + 1;
}
}
public void print() {
for (int i = 0; i < heapSize; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
请注意，我只翻译了代码部分，不包含问题的回答。
英文:
Am trying to implement min Heap using arrays. The problem am facing is when i poll an element technically it should return an minimum element from the Heap.
<br> But using the code i wrote it doesn't gives the minimum element
<br>Output:
<br>inserted heap: 1 3 2 6 4 5
Polledvlaue : 1
<br>New Heap after poll : 3 5 2 6 4
Polled value :3
<br>New Heap after poll : 4 5 2 6
Polled value :4
<br>New Heap after poll : 5 6 2
<br>Required output:
when polled it should give minimum Value
Main class code:
public class HeapApp {
public static void main(String[] args) {
Heap hg = new Heap(6);
hg.insert(6);
hg.insert(5);
hg.insert(4);
hg.insert(3);
hg.insert(2);
hg.insert(1);
System.out.print("inserted heap: ");
hg.print();
System.out.println();
System.out.println("Polledvlaue : "+hg.poll());
System.out.print("New Heap after poll : ");hg.print();
System.out.println();
System.out.println("Polled value :"+hg.poll());
System.out.print("New Heap after poll : "); hg.print();
System.out.println();
System.out.println("Polled value :"+hg.poll());
System.out.print("New Heap after poll : ");hg.print();
}
}
Heap Class:
public class Heap {
private int heapSize;
private int arr[];
Heap(int capacity){
heapSize = 0;
arr = new int[capacity];
}
public boolean isFull() {
return heapSize == arr.length;
}
public boolean isEmpty() {
return heapSize == 0;
}
public void insert(int element) {
if(isFull()) {
throw new RuntimeException("Heap is full");
}
arr[heapSize] = element;
heapSize++;
heapifyUp();
}
private void heapifyUp() {
int index = heapSize-1;
while(index > 0 ) {
if( arr[(index-1)/2] > arr[index]) {
int temp = arr[index];
arr[index] = arr[(index-1)/2];
arr[(index-1)/2] = temp;
index = (index-1)/2;
}else {
break;
}
}
}
public int poll() {
if(isEmpty())
throw new RuntimeException("Heap is empty");
int ans = arr[0];
arr[0] = arr[heapSize-1];
heapSize--;
heapifyDown();
return ans;
}
private void heapifyDown() {
int index = 0;
int left = 2*index+1;
while(left < heapSize) {
int min = left ; int right = ++left;
if(right < heapSize) {
if(arr[left] > arr[right]) {
min++;
}
}
if(arr[index] > arr[min]) {
int temp = arr[min];
arr[min] = arr[index];
arr[index] = temp;
}
index = min;
left = 2*index+1;
}
}
public void print() {
for(int i = 0 ; i < heapSize ; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
答案1
得分: 1
private void heapifyDown() {
int index = 0;
int left = 2 * index + 1;
while (left < heapSize) {
int min = left;
int right = left + 1; // <------ 这里是你的 bug。
if (right < heapSize) {
if (arr[left] > arr[right]) {
min++;
}
}
if (arr[index] > arr[min]) {
int temp = arr[min];
arr[min] = arr[index];
arr[index] = temp;
}
index = min;
left = 2 * index + 1;
}
}
英文:
private void heapifyDown() {
int index = 0;
int left = 2*index+1;
while(left < heapSize) {
int min = left ; int right = ++left; // <------ Here's your bug.
if(right < heapSize) {
if(arr[left] > arr[right]) {
min++;
}
}
if(arr[index] > arr[min]) {
int temp = arr[min];
arr[min] = arr[index];
arr[index] = temp;
}
index = min;
left = 2*index+1;
}
}
The ++left is incrementing both left and right to the same value.
Change that to int right = left + 1;
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论