查看: 133|回复: 0

[Java学习] java实现堆的操作方法(建堆,插入,删除)

发表于 3 天前

如下所示:

  1. import java.util.Arrays;
  2. //小顶堆的代码实现
  3. public class Heap {
  4. // 向下调整,顶端的大值往下调,主要用于删除和建堆,i表示要调整的节点索引,n表示堆的最有一个元素索引
  5. // 删除时候,i是0,建堆时候i从最后一个节点的父节点依次往前调整
  6. public static void fixDown(int[] data, int i, int n) {
  7. int num = data[i];
  8. int son = i * 2 + 1;
  9. while (son <= n) {
  10. if (son + 1 <= n && data[son + 1] < data[son])
  11. son++;
  12. if (num < data[son])
  13. break;
  14. data[i] = data[son];
  15. i = son;
  16. son = i * 2 + 1;
  17. }
  18. data[i] = num;
  19. }
  20. // 向上调整,小值往上走,用于增加,往上调整不需要制定最上面的索引,肯定是0
  21. public static void fixUp(int[] data, int n) {
  22. int num = data[n];
  23. int father = (n - 1) / 2;
  24. // data[father] > num是进入循环的基本条件,father减到0就不会减少了
  25. // 当n等于0时,father=0;进入死循环,所以当n==0时,需要跳出循环
  26. while (data[father] > num && n != 0) {
  27. data[n] = data[father];
  28. n = father;
  29. father = (n - 1) / 2;
  30. }
  31. data[n] = num;
  32. }
  33. // 删除,n表示堆的最后一个元素的索引
  34. public static void delete(int[] data, int n) {
  35. data[0] = data[n];
  36. data[n] = -1;
  37. fixDown(data, 0, n - 1);
  38. }
  39. // 增加,i表示要增加的数字,n表示增加位置的索引,是堆的最后一个元素
  40. public static void insert(int[] data, int num, int n) {
  41. data[n] = num;
  42. fixUp(data, n);
  43. }
  44. // 建堆,n表示要建堆的最后一个元素的索引
  45. public static void creat(int[] data, int n) {
  46. for (int i = (n - 1) / 2; i >= 0; i--)
  47. fixDown(data, i, n);
  48. }
  49. public static void main(String[] args) {
  50. int[] data = { 15, 13, 1, 5, 20, 12, 8, 9, 11 };
  51. // 测试建堆
  52. creat(data, data.length - 1);
  53. System.out.println(Arrays.toString(data));
  54. // 测试删除
  55. delete(data, data.length - 1);
  56. delete(data, data.length - 2);
  57. System.out.println(Arrays.toString(data));
  58. // 测试插入
  59. insert(data, 3, data.length - 2);
  60. System.out.println(Arrays.toString(data));
  61. }
  62. }
复制代码

以上这篇java实现堆的操作方法(建堆,插入,删除)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持程序员之家。



回复

使用道具 举报