最小堆的数组实现，使用Java语言。

huangapple
go评论97阅读模式
英文:

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

期望输出：
在轮询时应该返回最小值

主类代码：

  1. public class HeapApp {
  2.     public static void main(String[] args) {
  3.         Heap hg = new Heap(6);
  4.         hg.insert(6);
  5.         hg.insert(5);
  6.         hg.insert(4);
  7.         hg.insert(3);
  8.         hg.insert(2);
  9.         hg.insert(1);
  10.         System.out.print("插入堆：");
  11.         hg.print();
  12.         System.out.println();
  13.         System.out.println("轮询值：" + hg.poll());
  14.         System.out.print("轮询后的新堆：");
  15.         hg.print();
  16.         System.out.println();
  17.         System.out.println("轮询值：" + hg.poll());
  18.         System.out.print("轮询后的新堆：");
  19.         hg.print();
  20.         System.out.println();
  21.         System.out.println("轮询值：" + hg.poll());
  22.         System.out.print("轮询后的新堆：");
  23.         hg.print();
  24.     }
  25. }

堆类：

  1. public class Heap {
  2.     private int heapSize;
  3.     private int arr[];
  5.     Heap(int capacity) {
  6.         heapSize = 0;
  7.         arr = new int[capacity];
  8.     }
  10.     public boolean isFull() {
  11.         return heapSize == arr.length;
  12.     }
  14.     public boolean isEmpty() {
  15.         return heapSize == 0;
  16.     }
  18.     public void insert(int element) {
  19.         if (isFull()) {
  20.             throw new RuntimeException("堆已满");
  21.         }
  22.         arr[heapSize] = element;
  23.         heapSize++;
  24.         heapifyUp();
  25.     }
  27.     private void heapifyUp() {
  28.         int index = heapSize - 1;
  29.         while (index > 0) {
  30.             if (arr[(index - 1) / 2] > arr[index]) {
  31.                 int temp = arr[index];
  32.                 arr[index] = arr[(index - 1) / 2];
  33.                 arr[(index - 1) / 2] = temp;
  34.                 index = (index - 1) / 2;
  35.             } else {
  36.                 break;
  37.             }
  38.         }
  39.     }
  41.     public int poll() {
  42.         if (isEmpty())
  43.             throw new RuntimeException("堆为空");
  44.         int ans = arr[0];
  45.         arr[0] = arr[heapSize - 1];
  46.         heapSize--;
  47.         heapifyDown();
  48.         return ans;
  49.     }
  51.     private void heapifyDown() {
  52.         int index = 0;
  53.         int left = 2 * index + 1;
  54.         while (left < heapSize) {
  55.             int min = left;
  56.             int right = ++left;
  57.             if (right < heapSize) {
  58.                 if (arr[left] > arr[right]) {
  59.                     min++;
  60.                 }
  61.             }
  62.             if (arr[index] > arr[min]) {
  63.                 int temp = arr[min];
  64.                 arr[min] = arr[index];
  65.                 arr[index] = temp;
  66.             }
  67.             index = min;
  68.             left = 2 * index + 1;
  69.         }
  70.     }
  72.     public void print() {
  73.         for (int i = 0; i < heapSize; i++) {
  74.             System.out.print(arr[i] + " ");
  75.         }
  76.         System.out.println();
  77.     }
  78. }

请注意，我只翻译了代码部分，不包含问题的回答。

英文:

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:

  1. public class HeapApp {
  2. public static void main(String[] args) {
  3. Heap hg = new Heap(6);
  4. hg.insert(6);
  5. hg.insert(5);
  6. hg.insert(4);
  7. hg.insert(3);
  8. hg.insert(2);
  9. hg.insert(1);
  10. System.out.print(&quot;inserted heap: &quot;);
  11. hg.print();
  12. System.out.println();
  13. System.out.println(&quot;Polledvlaue : &quot;+hg.poll());
  14. System.out.print(&quot;New Heap after poll : &quot;);hg.print();
  15. System.out.println();
  16. System.out.println(&quot;Polled value :&quot;+hg.poll());
  17. System.out.print(&quot;New Heap after poll : &quot;); hg.print();
  18. System.out.println();
  19. System.out.println(&quot;Polled value :&quot;+hg.poll());
  20. System.out.print(&quot;New Heap after poll : &quot;);hg.print();
  21. }
  22. }

Heap Class:

  1. public class Heap {
  2. private int heapSize;
  3. private int arr[];
  4. Heap(int capacity){
  5. heapSize = 0;
  6. arr = new int[capacity];
  7. }
  8. public boolean isFull() {
  9. return heapSize == arr.length;
  10. }
  11. public boolean isEmpty() {
  12. return heapSize == 0;
  13. }
  14. public void insert(int element) {
  15. if(isFull()) {
  16. throw new RuntimeException(&quot;Heap is full&quot;);
  17. }
  18. arr[heapSize] = element;
  19. heapSize++;
  20. heapifyUp();
  21. }
  22. private void heapifyUp() {
  23. int index = heapSize-1;
  24. while(index &gt; 0 ) {
  25. if( arr[(index-1)/2] &gt; arr[index]) {
  26. int temp = arr[index];
  27. arr[index] = arr[(index-1)/2];
  28. arr[(index-1)/2] = temp;
  29. index = (index-1)/2;	
  30. }else {
  31. break;
  32. }
  33. }
  34. }
  35. public int poll() {
  36. if(isEmpty())
  37. throw new RuntimeException(&quot;Heap is empty&quot;);
  38. int ans = arr[0];
  39. arr[0] = arr[heapSize-1];
  40. heapSize--;
  41. heapifyDown();
  42. return ans;
  43. }
  44. private void heapifyDown() {
  45. int index = 0;
  46. int left = 2*index+1;
  47. while(left &lt; heapSize) {
  48. int min = left ; int right = ++left;
  49. if(right &lt; heapSize) {
  50. if(arr[left] &gt; arr[right]) {
  51. min++;
  52. }
  53. }
  54. if(arr[index] &gt; arr[min]) {
  55. int temp = arr[min];
  56. arr[min] = arr[index];
  57. arr[index] = temp;
  58. }
  59. index = min;
  60. left = 2*index+1;
  61. }
  62. }
  63. public void print() {
  64. for(int i = 0 ; i &lt; heapSize ; i++) {
  65. System.out.print(arr[i]+&quot; &quot;);
  66. }
  67. System.out.println();
  68. }
  69. }

答案1

得分: 1

  1. private void heapifyDown() {
  2.     int index = 0;
  3.     int left = 2 * index + 1;
  4.     while (left < heapSize) {
  5.         int min = left;
  6.         int right = left + 1; // <------ 这里是你的 bug。
  7.         if (right < heapSize) {
  8.             if (arr[left] > arr[right]) {
  9.                 min++;
  10.             }
  11.         }
  12.         if (arr[index] > arr[min]) {
  13.             int temp = arr[min];
  14.             arr[min] = arr[index];
  15.             arr[index] = temp;
  16.         }
  17.         index = min;
  18.         left = 2 * index + 1;
  19.     }
  20. }
英文: 
  1. private void heapifyDown() {
  2. int index = 0;
  3. int left = 2*index+1;
  4. while(left &lt; heapSize) {
  5. int min = left ; int right = ++left; // &lt;------ Here&#39;s your bug.
  6. if(right &lt; heapSize) {
  7. if(arr[left] &gt; arr[right]) {
  8. min++;
  9. }
  10. }
  11. if(arr[index] &gt; arr[min]) {
  12. int temp = arr[min];
  13. arr[min] = arr[index];
  14. arr[index] = temp;
  15. }
  16. index = min;
  17. left = 2*index+1;
  18. }
  19. }

The ++left is incrementing both left and right to the same value.

Change that to int right = left + 1;

huangapple
  • 本文由 发表于 2020年8月18日 20:46:53
  • 转载请务必保留本文链接：https://go.coder-hub.com/63468958.html
  • data-structures
  • heap
  • java
  • min-heap
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定