查看原文
其他

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

倪升武 程序员私房菜 2018-12-04


阅读本文大概需要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


这里不仅仅有技术


相关推荐阅读:

如果让你手写个栈和队列,你还会写吗?

开发了那么多项目,你能自己手写个健壮的链表出来吗?

下次面试若再被问到二叉树,希望你能对答如流!

面试还在被红-黑树虐?看完这篇轻松搞定面试官

2-3-4树是如何解决二叉树中非平衡问题的?

读完这篇,希望你能真正理解什么是哈希表

我敢说,这图绝对跟你想象中的不太一样!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存