堆其实是个很简单的数据结构

阅读本文大概需要5分钟

说到堆这种数据结构，很多人的第一反应是感觉很复杂，其实不然，堆就是个优先级队列而已，或者，堆其实就是一种树。本文先讲原理，后面给出堆的实现代码。

优先级队列可以用有序数组来实现，这种做法的问题是，尽管删除最大数据项的时间复杂度为O(1)，但是插入还是需要较长的O(N)时间，这是因为必须移动数组中平均一半的数据项以插入新数据项，并在完成插入后，数组依然有序。

本文主要介绍实现优先级队列的另一种结构：堆。堆是一种树，并非java和C++等编译语言里的“堆”。由它实现的优先级队列的插入和删除的时间复杂度都是O(logN)。尽管这样删除的时间变慢了一些，但是插入的时间快的多了。当速度非常重要，且有很多插入操作是，可以选择堆来实现优先级队列。堆有如下特点：

• 它是完全二叉树。即除了树的最后一层节点不需要是满的外，其他的每一层从左到右都完全是满的。

• 它常常用一个数组实现。用数组实现的完全二叉树中，节点的索引有如下特点（设该节点的索引为x）：
  它的父节点的索引为 (x-1) / 2； 它的左子节点索引为 2x + 1； 它的右子节点索引为 2x + 2。

• 堆中每个节点的关键字都大于（或等于）这个节点的子节点的关键字。这也是堆中每个节点必须满足的条件。所以堆和二叉搜索树相比，是弱序的。

向堆中插入数据，首先将数据项存放到叶节点中（即存到数组的最后一项），然后从该节点开始，逐级向上调整，直到满足堆中节点关键字的条件为止。

从堆中删除数据与插入不同，删除时永远删除根节点的数据，因为根节点的数据最大，删除完后，将最后一个叶节点移到根的位置，然后从根开始，逐级向下调整，直到满足堆中节点关键字的条件为止。

原理就这么多，堆真的很简单。

下面给出堆的实现代码：

1. public class Heap {

2.    private Node[] heapArray;

3.    private int maxSize;

4.    private int currentSize;

5.    public Heap(int mx) {

6.        maxSize = mx;

7.        currentSize = 0;

8.        heapArray = new Node[maxSize];

9.    }

10.    public boolean isEmpty() {

11.        return (currentSize == 0)? true : false;

12.    }

13.    public boolean isFull() {

14.        return (currentSize == maxSize)? true : false;

15.    }

16.    public boolean insert(int key) {

17.        if(isFull()) {

18.            return false;

19.        }

20.        Node newNode = new Node(key);

21.        heapArray[currentSize] = newNode;

22.        trickleUp(currentSize++);

23.        return true;

24.    }

25.    //向上调整

26.    public void trickleUp(int index) {

27.        int parent = (index - 1) / 2; //父节点的索引

28.        Node bottom = heapArray[index]; //将新加的尾节点存在bottom中

29.        while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) {

30.            heapArray[index] = heapArray[parent];

31.            index = parent;

32.            parent = (parent - 1) / 2;

33.        }

34.        heapArray[index] = bottom;

35.    }

36.    public Node remove() {

37.        Node root = heapArray[0];

38.        heapArray[0] = heapArray[--currentSize];

39.        trickleDown(0);

40.        return root;

41.    }

42.    //向下调整

43.    public void trickleDown(int index) {

44.        Node top = heapArray[index];

45.        int largeChildIndex;

46.        while(index < currentSize/2) { //while node has at least one child

47.            int leftChildIndex = 2 * index + 1;

48.            int rightChildIndex = leftChildIndex + 1;

49.            //find larger child

50.            if(rightChildIndex < currentSize &&  //rightChild exists?

51.                    heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) {

52.                largeChildIndex = rightChildIndex;

53.            }

54.            else {

55.                largeChildIndex = leftChildIndex;

56.            }

57.            if(top.getKey() >= heapArray[largeChildIndex].getKey()) {

58.                break;

59.            }

60.            heapArray[index] = heapArray[largeChildIndex];

61.            index = largeChildIndex;

62.        }

63.        heapArray[index] = top;

64.    }

65.    //根据索引改变堆中某个数据

66.    public boolean change(int index, int newValue) {

67.        if(index < 0 || index >= currentSize) {

68.            return false;

69.        }

70.        int oldValue = heapArray[index].getKey();

71.        heapArray[index].setKey(newValue);

72.        if(oldValue < newValue) {

73.            trickleUp(index);

74.        }

75.        else {

76.            trickleDown(index);

77.        }

78.        return true;

79.    }

80.    public void displayHeap() {

81.        System.out.println("heapArray(array format): ");

82.        for(int i = 0; i < currentSize; i++) {

83.            if(heapArray[i] != null) {

84.                System.out.print(heapArray[i].getKey() + " ");

85.            }

86.            else {

87.                System.out.print("--");

88.            }

89.        }

90.    }

91. }

92. class Node {

93.    private int iData;

94.    public Node(int key) {

95.        iData = key;

96.    }

97.    public int getKey() {

98.        return iData;

99.    }

100.    public void setKey(int key) {

101.        iData = key;

102.    }

103. }

这个实现的代码，可以在等公交的时候、吃饭排队的时候拿来看看，利用碎片化时间来学习。

END

这里不仅仅有技术

相关推荐阅读：