一、为什么二叉堆利用数组存储

堆逻辑结构最大的优势就在于，通过数组，目标index 能推算出 父子指针的定位。所以在上下heaptify的时候可以直接找到对应位置进行交换等操作。现有语言里比如Java,C,C+；以java为例：系统层面API:PriorityQueue ”优先队列“,底层实现就是堆结构。

但是大部分堆API都没有提供动态修改已排序对象内部值的方法 Resign();

#举例 已排序堆数组arr[];其中元素为Object O, 并且O包含N个属性，比如以age属性为例

arr[O1,O2,O3…] 这里装着一堆object同学对象，现在以同学对象的age属性，给arr排序

/**

* 需求是，我给O3的age调整，比如改成20岁，对象要变更内部值。

* 要求O3调整完毕后，提供一个方法，保证arr[]依然是排序后的堆结构。

* ###动态修改，动态增删，这种其实现实中很常见的需求。

* 关键还在于，我们需要时间复杂度。

* O(logN) 复杂度

*/

– 逻辑过程简单想一下就知道 插入一个值，然后每次O对象都要从下往上/从上往下进行heaptify这个操作，而且要进行N次

所以大部分都觉得动态修改这个代价太大。

回到正题，如果想实现O(logN)时间复杂度的堆，就需要有一个IndexMap:目的每次记录修改前的值在堆内的哪个 ”位置“ 。

我个人认为正是由于数组的下标，标记了父子对应关系的可预见性数学方程关系:

[0,1,2,3,4,5]前提以0位置开始

1. left  = 2*i + 1;

2. right = 2*i + 2;

3. root =  (i – 1)/2;

才方便找到。

链表实现对应关系，可能会使用更多数据结构占用。

附带数组Heap Resign();

package class04;

import java.util.ArrayList;

import java.util.Comparator;

import java.util.HashMap;

import java.util.PriorityQueue;

public class Heap {

    // 堆

    public static class MyHeap {

       private ArrayList heap;

       private HashMap indexMap;

       private int heapSize;

       private Comparator comparator;

       public MyHeap(Comparator com) {

           heap = new ArrayList<>();

           indexMap = new HashMap<>();

           heapSize = 0;

           comparator = com;

       }

       public boolean isEmpty() {

           return heapSize == 0;

       }

       public int size() {

           return heapSize;

       }

       public boolean contains(T key) {

           return indexMap.containsKey(key);

       }

       public void push(T value) {

           heap.add(value);

           indexMap.put(value, heapSize);

           heapInsert(heapSize++);

       }

       public T pop() {

           T ans = heap.get(0);

           int end = heapSize – 1;

           swap(0, end);

           heap.remove(end);

           indexMap.remove(ans);

           heapify(0, –heapSize);

           return ans;

       }

       public void resign(T value) {

           int valueIndex = indexMap.get(value);

           heapInsert(valueIndex);

           heapify(valueIndex, heapSize);

       }

       private void heapInsert(int index) {

           while (comparator.compare(heap.get(index), heap.get((index – 1) / 2)) < 0) {

              swap(index, (index – 1) / 2);

              index = (index – 1) / 2;

           }

       }

       private void heapify(int index, int heapSize) {

           int left = index * 2 + 1;

           while (left < heapSize) {

              int largest = left + 1 < heapSize && (comparator.compare(heap.get(left + 1), heap.get(left)) < 0)

                     ? left + 1

                     : left;

              largest = comparator.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index;

              if (largest == index) {

                  break;

              }

              swap(largest, index);

              index = largest;

              left = index * 2 + 1;

           }

       }

       private void swap(int i, int j) {

           T o1 = heap.get(i);

           T o2 = heap.get(j);

           heap.set(i, o2);

           heap.set(j, o1);

           indexMap.put(o1, j);

           indexMap.put(o2, i);

       }

    }

    public static class Student {

       public int classNo;

       public int age;

       public int id;

       public Student(int c, int a, int i) {

           classNo = c;

           age = a;

           id = i;

       }

    }

    public static class StudentComparator implements Comparator {

       @Override

       public int compare(Student o1, Student o2) {

           return o1.age – o2.age;

       }

    }

    public static void main(String[] args) {

       Student s1 = null;

       Student s2 = null;

       Student s3 = null;

       Student s4 = null;

       Student s5 = null;

       Student s6 = null;

       s1 = new Student(2, 50, 11111);

       s2 = new Student(1, 60, 22222);

       s3 = new Student(6, 10, 33333);

       s4 = new Student(3, 20, 44444);

       s5 = new Student(7, 72, 55555);

       s6 = new Student(1, 14, 66666);

       PriorityQueue heap = new PriorityQueue<>(new StudentComparator());

       heap.add(s1);

       heap.add(s2);

       heap.add(s3);

       heap.add(s4);

       heap.add(s5);

       heap.add(s6);

       while (!heap.isEmpty()) {

           Student cur = heap.poll();

           System.out.println(cur.classNo + “,” + cur.age + “,” + cur.id);

       }

       System.out.println(“===============”);

       MyHeap myHeap = new MyHeap<>(new StudentComparator());

       myHeap.push(s1);

       myHeap.push(s2);

       myHeap.push(s3);

       myHeap.push(s4);

       myHeap.push(s5);

       myHeap.push(s6);

       while (!myHeap.isEmpty()) {

           Student cur = myHeap.pop();

           System.out.println(cur.classNo + “,” + cur.age + “,” + cur.id);

       }

       System.out.println(“===============”);

       s1 = new Student(2, 50, 11111);

       s2 = new Student(1, 60, 22222);

       s3 = new Student(6, 10, 33333);

       s4 = new Student(3, 20, 44444);

       s5 = new Student(7, 72, 55555);

       s6 = new Student(1, 14, 66666);

       heap = new PriorityQueue<>(new StudentComparator());

       heap.add(s1);

       heap.add(s2);

       heap.add(s3);

       heap.add(s4);

        heap.add(s5);

       heap.add(s6);

       s2.age = 6;

       s4.age = 12;

       s5.age = 10;

       s6.age = 84;

       while (!heap.isEmpty()) {

           Student cur = heap.poll();

           System.out.println(cur.classNo + “,” + cur.age + “,” + cur.id);

       }

       System.out.println(“===============”);

       s1 = new Student(2, 50, 11111);

       s2 = new Student(1, 60, 22222);

       s3 = new Student(6, 10, 33333);

       s4 = new Student(3, 20, 44444);

       s5 = new Student(7, 72, 55555);

       s6 = new Student(1, 14, 66666);

       myHeap = new MyHeap<>(new StudentComparator());

       myHeap.push(s1);

       myHeap.push(s2);

       myHeap.push(s3);

       myHeap.push(s4);

       myHeap.push(s5);

       myHeap.push(s6);

       s2.age = 6;

       myHeap.resign(s2);

       s4.age = 12;

       myHeap.resign(s4);

       s5.age = 10;

       myHeap.resign(s5);

       s6.age = 84;

       myHeap.resign(s6);

       while (!myHeap.isEmpty()) {

           Student cur = myHeap.pop();

           System.out.println(cur.classNo + “,” + cur.age + “,” + cur.id);

       }

       // 对数器

       System.out.println(“test begin”);

       int maxValue = 100000;

       int pushTime = 1000000;

       int resignTime = 100;

       MyHeap test = new MyHeap<>(new StudentComparator());

       ArrayList list = new ArrayList<>();

       for(int i = 0 ; i < pushTime; i++) {

          Student cur = new Student(1,(int) (Math.random() * maxValue), 1000);

           list.add(cur);

           test.push(cur);

       }

       for(int i = 0 ; i < resignTime; i++) {

           int index = (int)(Math.random() * pushTime);

           list.get(index).age = (int) (Math.random() * maxValue);

           test.resign(list.get(index));

       }

       int preAge = Integer.MIN_VALUE;

       while(test.isEmpty()) {

           Student cur = test.pop();

           if(cur.age < preAge) {

              System.out.println(“Oops!”);

           }

           preAge = cur.age;

       }

       System.out.println(“test finish”);

    }

}

延伸阅读：

二、存储结构

逻辑结构主要用于算法设计，而存储结构用于指导算法编程实现。存储结构有基本的两种结构：

顺序存储：逻辑上相邻的元素存储在物理位置相邻的存储单元中

链式存储：在数据元素中添加一些地址域或辅助结构，用于存放数据元素之间的关系。

顺序存储结构在内存中的地址是连续的，所以存取速度很快，但是在插入或删除操作效率低，因为插入或删除操作会移动数据元素。

链式存储结构在内存中地址可以是不连续的，插入和删除操作效率高，因为增加了寻址的操作，所以查找和遍历效率低。

同样的逻辑结构（线性、树形、图形、集合）既可以采用顺序存储结构也可以采用链式存储结构来存储数据和关系。存储结构的选择主要考虑算法的效率，算法的时间和空间哪个更好，具体选择哪种和需求有关，基本存储结构既可以单独使用，也可以组合使用。

上一篇

B+树查询的稳定性为什么重要?

下一篇

trello是哪个公司的?