#堆

what ? why ? when ? how ?

##why

为什么要用堆？
##what

什么是堆？
堆有什么特点？
##how
如何操作堆（建立、插入、删除、查找）？
##when

##什么是堆？
堆是特殊的“队列”，从堆中取出元素是按照元素优先级大小，而不是元素进入队列的先后顺序。
堆是一颗完全二叉树，其结点的值大于或小于其子结点的值（大于是最大堆 小于是最小堆）。
最大堆：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1T8Qs0o2-1603163463755)(https://i.imgur.com/iNt7VPc.png)]
最小堆：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e3hC0mKJ-1603163463757)(https://i.imgur.com/WZtNa6D.png)]
##为什么要用堆？

堆也被称为“优先队列”。 比如做事情：事情 A 明天需要完成，事情 B 这周需要完成，事情 C 这个月需要完成。 事情 A 、 B 、 C 出现的顺序是 C 早于 B 早于 C ，正常情况下都将 A 置为优先级最高，B 其次，C 最低。虽然事情 C 最先知道要做但是由于优先级（时间紧迫）需要先把事件 A 先完成。
##堆有什么特点？
堆的两个特性：
结构性：用数组表示的完全二叉树；
有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)。
##如何操作堆（建立、插入、删除、判空、判满）？
最大堆的操作
class Heap {
int[] data; //存储元素
int size;   //堆中当前元素的个数
int capacity;   //堆的最大容量
}

###建立
/**
 * 创建堆
 *
 * @param capacity
 * @return
 */
public static Heap createHeap(int capacity) {
    if (capacity <= 0) {
        System.out.println("创建失败：capacity 值为0或负数");
        return null;
    }
    Heap heap = new Heap();
    heap.data = new int[capacity + 1];
    heap.size = 0;
    heap.capacity = capacity;
    return heap;
}

###判空
    /**
 * 堆是否为空
 *
 * @param heap
 * @return
 */
public boolean isEmpty(Heap heap) {
    if (heap == null) {
        System.out.println("Heap is null.");
        return false;
    }
    return heap.size == 0;
}

###判满
    /**
 * 堆中元素是否满了
 *
 * @param heap
 * @return
 */
public boolean isFull(Heap heap) {
    if (heap == null) {
        System.out.println("Heap is null.");
        return false;
    }
    return heap.size == heap.capacity;
}

###插入
思路：
插入最后面比较该节点值和其父亲结点值大小，如果比其父亲结点值大换 一直判断到根。
/**
 * 往堆中插入元素
 *
 * @param heap
 * @param element
 * @return
 */
public boolean insert(Heap heap, int element) {
    if (heap == null) {
        System.out.println("Heap is null. 插入失败");
        return false;
    } else if (isFull(heap)) {
        System.out.println("堆满了,插入失败");
        return false;
    }
    int i = 0;
    i = ++heap.size;
    for (; element > heap.data[i / 2] && i > 1; i = i / 2) {
        heap.data[i] = heap.data[i / 2];
    }
    //插入元素
    heap.data[i] = element;
    return true;
}

###删除堆中的最大值
思路：

将最后一个节点的值替换根结点值然后判断其子节点的值是否比其大，如果比它大换 一直往下判断到其子节点比其小或到最后。
/**
 * 删除堆中的最大值
 *
 * @param heap
 * @return
 */
public int deleteMax(Heap heap) {
    if (heap.isEmpty(heap)) {
        System.out.println("堆为空");
        return -1;
    }
    //读取堆中的最大元素
    int maxElement = heap.data[1];
    //获取堆中最后一个元素并将当前个数减少1
    int lastElement = heap.data[heap.size--];
    int parent=1,child;
    for (; parent * 2 <= heap.size; parent = child) {
        child = parent * 2;
        if (child != heap.size && heap.data[child] < heap.data[child + 1]) {
            child++;//指向左右孩子结点较大者
        }
        if (lastElement >= heap.data[child] ){
            //找到合适的位置
            break;
        }else{
            //在往下找调整
            heap.data[parent] = heap.data[child];
        }
    }
    heap.data[parent]=lastElement;
    return maxElement;
}

###按层遍历
/**
 * 按层遍历堆
 * @param heap
 */
public void layerTraversal(Heap heap){
    if(heap==null){
        System.out.println("Heap is null");
        return;
    }
    int layer=1,num=1;
    while(num<=heap.size){
        //每层的数量
        int layerNum=(int)(Math.pow(2,layer-1));
        for(int i=0;i<layerNum && num<=heap.size;i++){
            System.out.print("--------"+heap.data[num++]);
        }
        System.out.println();
        layer++;
    }
}

##结果
	Heap heap=Heap.createHeap(100);
    int [] data={100,34,67,78,98,55,44};
    for (int i = 0; i < data.length; i++) {
        if(heap.insert(heap,data[i])){
        }else{
            System.out.println("插入失败");
            break;
        }
    }
    heap.layerTraversal(heap);
    System.out.println("MaxElement: "+heap.deleteMax(heap));
    heap.layerTraversal(heap);

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-shjrq8Ja-1603163463759)(https://i.imgur.com/f38xvan.png)]
##最大堆的建立
记得阿里面试的时候问到过自己没有回答好… 现在想起来应该这样回答
方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为 O(NlogN).
方法2：在线性时间复杂度下建立最大堆。

将N个元素按输入顺序存入，先满足完全二叉树的结构特性
调整各结点位置，以满足最大堆的有序特性。

方法2
public void buildMaxHeap(Heap heap, int[] data) {
    if (heap == null) {
        System.out.println("Heap is null");
        return;
    }
    if ((heap.capacity - heap.size) < data.length) {
        System.out.println("堆容量不足");
        return;
    }
    for (int i = 0; i < data.length; i++) {
        heap.data[++size] = data[i];
    }

    for (int i = heap.size / 2; i > 0; i--) {
        percDown(heap, i);
    }
}

//调整
public void percDown(Heap heap, int p) {
    int parent, child;
    int temp = heap.data[p];
    for (parent = p; parent * 2 <= heap.size; parent = child) {
        child = parent * 2;
        if (child != heap.size && heap.data[child+1] > heap.data[child]) {
            //指向左右结点较大者
            child++;
        }
        if (temp > heap.data[child]) {
            break;
        } else {
            heap.data[parent] = heap.data[child];
        }
    }
    heap.data[parent] = temp;
}

###证明方法 2 建造最大堆时间复杂度为 O(N)
若二叉树高为 h ，是一棵满二叉树 (堆是一棵完全二叉树结点数一定小于满二叉树)，那么结点的个数是 n=2^h -1
最后一层节点数 2^(h-1) 个， 最后第二层 2^(h-2) 个 … 第一层 2^(h-h) 个
2^(h-2) 个结点向下访问一次，2^(h-3) 个结点向下访问两次… 1 个结点向下访问 h-1 次。
公式推导：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-escvy9tr-1603163463760)(https://i.imgur.com/uWb6Ft6.jpg)]
源代码：https://github.com/rookieLJ/Tree.git
TestHeap.java

#总结

参考

数据结构 陈越 何钦铭

https://blog.csdn.net/anonymalias/article/details/8807895

堆是一个“优先队列”。
堆的特点：完全二叉树、每个结点大于或小于其子结点的值。从根结点到任意结点路径上结点序列的有序性。
最大堆的建立（第二种方法），时间复杂度 O(N)。

有什么问题欢迎指出，感谢！

Java内存分配原理


栈、堆、常量池虽同属Java内存分配时操作的区域，但其适用范围和功用却大不相同。

一般Java在内存分配时会涉及到以下区域：

◆寄存器：我们在程序中无法控制

◆栈：存放基本类型的数据和对象的引用，但对象本身不存放在栈中，而是存放在堆中

◆堆：存放用new产生的数据

◆静态域：存放在对象中用static定义的静态成员

◆常量池：存放常量

◆非RAM存储：硬盘等永久存储空间

Java内存分配中的栈

在函数中定义的一些基本类型的变量数据和对象的引用变量都在函数的栈内存中分配。

  

当在一段代码块定义一个变量时，Java就在栈中 为这个变量分配内存空间，当该变量退出该作用域后，Java会自动释放掉为该变量所分配的内存空间，该内存空间可以立即被另作他用。

Java内存分配中的堆

堆内存用来存放由new创建的对象和数组。 在堆中分配的内存，由Java虚拟机的自动垃圾回收器来管理。

在堆中产生了一个数组或对象后，还可以 在栈中定义一个特殊的变量，让栈中这个变量的取值等于数组或对象在堆内存中的首地址，栈中的这个变量就成了数组或对象的引用变量。  引用变量就相当于是 为数组或对象起的一个名称，以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象。引用变量就相当于是为数组或者对象起的一个名称。

引用变量是普通的变量，定义时在栈中分配，引用变量在程序运行到其作用域之外后被释放。而数组和对象本身在堆中分配，即使程序 运行到使用 new 产生数组或者对象的语句所在的代码块之外，数组和对象本身占据的内存不会被释放，数组和对象在没有引用变量指向它的时候，才变为垃圾，不能在被使用，但仍 然占据内存空间不放，在随后的一个不确定的时间被垃圾回收器收走（释放掉）。这也是 Java 比较占内存的原因。

实际上，栈中的变量指向堆内存中的变量，这就是Java中的指针！


 
常量池 (constant pool)

常量池指的是在编译期被确定，并被保存在已编译的.class文件中的一些数据。除了包含代码中所定义的各种基本类型（如int、long等等）和对象型（如String及数组）的常量值(final)还包含一些以文本形式出现的符号引用，比如：

◆类和接口的全限定名；

◆字段的名称和描述符；

◆方法和名称和描述符。

虚拟机必须为每个被装载的类型维护一个常量池。常量池就是该类型所用到常量的一个有序集和，包括直接常量（string,integer和 floating point常量）和对其他类型，字段和方法的符号引用。

对于String常量，它的值是在常量池中的。而JVM中的常量池在内存当中是以表的形式存在的， 对于String类型，有一张固定长度的CONSTANT_String_info表用来存储文字字符串值，注意：该表只存储文字字符串值，不存储符号引 用。说到这里，对常量池中的字符串值的存储位置应该有一个比较明了的理解了。

在程序执行的时候,常量池 会储存在Method Area,而不是堆中。

堆与栈

Java的堆是一个运行时数据区,类的(对象从中分配空间。这些对象通过new、newarray、 anewarray和multianewarray等指令建立，它们不需要程序代码来显式的释放。堆是由垃圾回收来负责的，堆的优势是可以动态地分配内存 大小，生存期也不必事先告诉编译器，因为它是在运行时动态分配内存的，Java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态 分配内存，存取速度较慢。

栈的优势是，存取速度比堆要快，仅次于寄存器，栈数据可以共享。但缺点是，存在栈中的数据大小与生存期必须是 确定的，缺乏灵活性。栈中主要存放一些基本类型的变量数据（int, short, long, byte, float, double, boolean, char）和对象句柄(引用)。

栈有一个很重要的特殊性，就是存在栈中的数据可以共享。假设我们同时定义：

int a = 3;   
	
int b = 3；  
编译器先处理int a = 3；首先它会在栈中创建一个变量为a的引用，然后查找栈中是否有3这个值，如果没找到，就将3存放进来，然后将a指向3。接着处理int b = 3；在创建完b的引用变量后，因为在栈中已经有3这个值，便将b直接指向3。这样，就出现了a与b同时均指向3的情况。

这时，如果再令 a=4；那么编译器会重新搜索栈中是否有4值，如果没有，则将4存放进来，并令a指向4；如果已经有了，则直接将a指向这个地址。因此a值的改变不会影响 到b的值。

要注意这种数据的共享与两个对象的引用同时指向一个对象的这种共享是不同的，因为这种情况a的修改并不会影响到b, 它是由编译器完成的，它有利于节省空间。而一个对象引用变量修改了这个对象的内部状态，会影响到另一个对象引用变量。

String是一个特殊的包装类数据。可以用：

String str = new String("abc");   
	
String str = "abc";  
两种的形式来创建，第一种是用new()来新建对象的，它会在存放于堆中。每调用一次就会创建一个新的对象。而第二种是先在栈中创建一个对String类的对象引用变量str，然后通过符号引用去字符串常量池 里找有没有"abc",如果没有，则将"abc"存放进字符串常量池 ，并令str指向”abc”，如果已经有”abc” 则直接令str指向“abc”。

比较类里面的数值是否相等时，用equals()方法；当测试两个包装类的引用是否指向同一个对象时，用==，下面用例子说明上面的理论。

String str1 = "abc";   
String str2 = "abc";   
System.out.println(str1==str2); //true  

可以看出str1和str2是指向同一个对象的。

String str1 =new String ("abc");   

String str2 =new String ("abc");   

System.out.println(str1==str2); // false  

用new的方式是生成不同的对象。每一次生成一个。

因此用第二种方式创建多个”abc”字符串,在内存中 其实只存在一个对象而已. 这种写法有利与节省内存空间. 同时它可以在一定程度上提高程序的运行速度，因为JVM会自动根据栈中数据的实际情况来决定是否有必要创建新对象。而对于String str = new String("abc")；的代码，则一概在堆中创建新对象，而不管其字符串值是否相等，是否有必要创建新对象，从而加重了程序的负担。

另 一方面, 要注意: 我们在使用诸如String str = "abc"；的格式定义类时，总是想当然地认为，创建了String类的对象str。担心陷阱！对象可能并没有被创建！而可能只是指向一个先前已经创建的 对象。只有通过new()方法才能保证每次都创建一个新的对象。

 

由于String类的immutable性质，当String变量需要经常变换 其值时，应该考虑使用StringBuffer类，以提高程序效率。

 

1. 首先String不属于8种基本数据类型，String是一个对象。因为对象的默认值是null，所以String的默认值也是null；但它又是一种特殊的对象，有其它对象没有的一些特性。

2. new String()和new String(”")都是申明一个新的空字符串，是空串不是null；

3. String str=”kvill”；String str=new String (”kvill”)的区别

示例：

String s0="kvill";   

String s1="kvill";   

String s2="kv" + "ill";   

System.out.println( s0==s1 );   

System.out.println( s0==s2 );  

结果为：


true 

true

首先，我们要知结果为道Java 会确保一个字符串常量只有一个拷贝。

因为例子中的 s0和s1中的”kvill”都是字符串常量，它们在编译期就被确定了，所以s0==s1为true；而”kv”和”ill”也都是字符串常量，当一个字 符串由多个字符串常量连接而成时，它自己肯定也是字符串常量，所以s2也同样在编译期就被解析为一个字符串常量，所以s2也是常量池中” kvill”的一个引用。所以我们得出s0==s1==s2；用new String() 创建的字符串不是常量，不能在编译期就确定，所以new String() 创建的字符串不放入常量池中，它们有自己的地址空间。

示例：

String s0="kvill";   

String s1=new String("kvill");   

String s2="kv" + new String("ill");   

System.out.println( s0==s1 );   

System.out.println( s0==s2 );   

System.out.println( s1==s2 );  

结果为：


false 

false 

false

例2中s0还是常量池 中"kvill”的应用，s1因为无法在编译期确定，所以是运行时创建的新对象”kvill”的引用，s2因为有后半部分 new String(”ill”)所以也无法在编译期确定，所以也是一个新创建对象”kvill”的应用;明白了这些也就知道为何得出此结果了。

4. String.intern()：

再补充介绍一点：存在于.class文件中的常量池，在运行期被JVM装载，并且可以扩充。String的 intern()方法就是扩充常量池的 一个方法；当一个String实例str调用intern()方法时，Java 查找常量池中 是否有相同Unicode的字符串常量，如果有，则返回其的引用，如果没有，则在常 量池中增加一个Unicode等于str的字符串并返回它的引用；看示例就清楚了

示例：

String s0= "kvill";   

String s1=new String("kvill");   

String s2=new String("kvill");   

System.out.println( s0==s1 );   

System.out.println( "**********" );   

s1.intern();   

s2=s2.intern(); //把常量池中"kvill"的引用赋给s2   

System.out.println( s0==s1);   

System.out.println( s0==s1.intern() );   

System.out.println( s0==s2 );  

结果为：


false 

false //虽然执行了s1.intern(),但它的返回值没有赋给s1 

true //说明s1.intern()返回的是常量池中"kvill"的引用 

true

最后我再破除一个错误的理解：有人说，“使用 String.intern() 方法则可以将一个 String 类的保存到一个全局 String 表中 ，如果具有相同值的 Unicode 字符串已经在这个表中，那么该方法返回表中已有字符串的地址，如果在表中没有相同值的字符串，则将自己的地址注册到表中”如果我把他说的这个全局的 String 表理解为常量池的话，他的最后一句话，”如果在表中没有相同值的字符串，则将自己的地址注册到表中”是错的：

示例：

String s1=new String("kvill");   

String s2=s1.intern();   

System.out.println( s1==s1.intern() );   

System.out.println( s1+" "+s2 );   

System.out.println( s2==s1.intern() );  

结果：


false 

kvill kvill 

true

在这个类中我们没有声名一个”kvill”常量，所以常量池中一开始是没有”kvill”的，当我们调用s1.intern()后就在常量池中新添加了一 个”kvill”常量，原来的不在常量池中的”kvill”仍然存在，也就不是“将自己的地址注册到常量池中”了。

s1==s1.intern() 为false说明原来的”kvill”仍然存在；s2现在为常量池中”kvill”的地址，所以有s2==s1.intern()为true。

5. 关于equals()和==:

这个对于String简单来说就是比较两字符串的Unicode序列是否相当，如果相等返回true;而==是 比较两字符串的地址是否相同，也就是是否是同一个字符串的引用。

6. 关于String是不可变的

这一说又要说很多，大家只 要知道String的实例一旦生成就不会再改变了，比如说：String str=”kv”+”ill”+” “+”ans”; 就是有4个字符串常量，首先”kv”和”ill”生成了”kvill”存在内存中，然后”kvill”又和” ” 生成 “kvill “存在内存中，最后又和生成了”kvill ans”;并把这个字符串的地址赋给了str,就是因为String的”不可变”产生了很多临时变量，这也就是为什么建议用StringBuffer的原 因了，因为StringBuffer是可改变的。

下面是一些String相关的常见问题：

String中的final用法和理解


final StringBuffer a = new StringBuffer("111");

final StringBuffer b = new StringBuffer("222");

a=b;//此句编译不通过

final StringBuffer a = new StringBuffer("111");

a.append("222");// 编译通过

可见，final只对引用的"值"(即内存地址)有效，它迫使引用只能指向初始指向的那个对象，改变它的指向会导致编译期错误。至于它所指向的对象 的变化，final是不负责的。

String常量池问题的几个例子

下面是几个常见例子的比较分析和理解：

String a = "a1";   

String b = "a" + 1;   

System.out.println((a == b)); //result = true  

String a = "atrue";   

String b = "a" + "true";   

System.out.println((a == b)); //result = true  

String a = "a3.4";   

String b = "a" + 3.4;   

System.out.println((a == b)); //result = true 

分析：JVM对于字符串常量的"+"号连接，将程序编译期，JVM就将常量字符串的"+"连接优化为连接后的值，拿"a" + 1来说，经编译器优化后在class中就已经是a1。在编译期其字符串常量的值就确定下来，故上面程序最终的结果都为true。

String a = "ab";   

String bb = "b";   

String b = "a" + bb;   

System.out.println((a == b)); //result = false 

分析：JVM对于字符串引用，由于在字符串的"+"连接中，有字符串引用存在，而引用的值在程序编译期是无法确定的，即"a" + bb无法被编译器优化，只有在程序运行期来动态分配并将连接后的新地址赋给b。所以上面程序的结果也就为false。

String a = "ab";   

final String bb = "b";   

String b = "a" + bb;   

System.out.println((a == b)); //result = true 

分析：和[3]中唯一不同的是bb字符串加了final修饰，对于final修饰的变量，它在编译时被解析为常量值的一个本地拷贝存储到自己的常量 池中或嵌入到它的字节码流中。所以此时的"a" + bb和"a" + "b"效果是一样的。故上面程序的结果为true。

String a = "ab";   

final String bb = getBB();   

String b = "a" + bb;   

System.out.println((a == b)); //result = false   

private static String getBB() {  return "b";   } 

分析：JVM对于字符串引用bb，它的值在编译期无法确定，只有在程序运行期调用方法后，将方法的返回值和"a"来动态连接并分配地址为b，故上面 程序的结果为false。

通过上面4个例子可以得出得知：String  s  =  "a" + "b" + "c"; 就等价于String s = "abc";  


String  a  =  "a";   

String  b  =  "b";   

String  c  =  "c";   

String  s  =   a  +  b  +  c; 

这个就不一样了，最终结果等于： 

 

StringBuffer temp = new StringBuffer();     

temp.append(a).append(b).append(c);     

String s = temp.toString(); 

由上面的分析结果，可就不难推断出String 采用连接运算符（+）效率低下原因分析，形如这样的代码：

public class Test {  
    public static void main(String args[]) {  
        String s = null;  
        for(int i = 0; i < 100; i++) {  
        s += "a";  
        }  
    }  
} 

每做一次 + 就产生个StringBuilder对象，然后append后就扔掉。下次循环再到达时重新产生个StringBuilder对象，然后 append 字符串，如此循环直至结束。如果我们直接采用 StringBuilder 对象进行 append 的话，我们可以节省 N - 1 次创建和销毁对象的时间。所以对于在循环中要进行字符串连接的应用，一般都是用StringBuffer或StringBulider对象来进行 append操作。

String对象的intern方法理解和分析：

public class Test4 {  

    private static String a = "ab";   

    public static void main(String[] args){  

    String s1 = "a";  

    String s2 = "b";  

    String s = s1 + s2;  

    System.out.println(s == a);//false  

    System.out.println(s.intern() == a);//true    

    }  

} 

这里用到Java里面是一个常量池的问题。对于s1+s2操作，其实是在堆里面重新创建了一个新的对象,s保存的是这个新对象在堆空间的的内容，所 以s与a的值是不相等的。而当调用s.intern()方法，却可以返回s在常量池中的地址值，因为a的值存储在常量池中，故s.intern和a的值相等。

总结

栈中用来存放一些原始数据类型的局部变量数据和对象的引用(String,数组.对象等等)但不存放对象内容

堆中存放使用new关键字创建的对象.

字符串是一个特殊包装类,其引用是存放在栈里的,而对象内容必须根据创建方式不同定(常量池和堆).有的是编译期就已经创建好，存放在字符串常 量池中，而有的是运行时才被创建.使用new关键字，存放在堆中。

 

堆（Heap）与栈（Stack）是开发人员必须面对的两个概念，在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层含义：

（1）程序内存布局场景下，堆与栈表示两种内存管理方式；

（2）数据结构场景下，堆与栈表示两种常用的数据结构。
1.程序内存分区中的堆与栈
1.1 栈简介
栈由操作系统自动分配释放 ，用于存放函数的参数值、局部变量等，其操作方式类似于数据结构中的栈。参考如下代码：
int main() {
	int b;				//栈
	char s[] = "abc"; 	//栈
	char *p2;			//栈
}

其中函数中定义的局部变量按照先后定义的顺序依次压入栈中，也就是说相邻变量的地址之间不会存在其它变量。栈的内存地址生长方向与堆相反，由高到底，所以后定义的变量地址低于先定义的变量，比如上面代码中变量 s 的地址小于变量 b 的地址，p2 地址小于 s 的地址。栈中存储的数据的生命周期随着函数的执行完成而结束。
1.2 堆简介
堆由开发人员分配和释放， 若开发人员不释放，程序结束时由 OS 回收，分配方式类似于链表。参考如下代码：
int main() {
	// C 中用 malloc() 函数申请
	char* p1 = (char *)malloc(10);
	cout<<(int*)p1<<endl;		//输出：00000000003BA0C0
	
	// 用 free() 函数释放
	free(p1);
   
	// C++ 中用 new 运算符申请
	char* p2 = new char[10];
	cout << (int*)p2 << endl;		//输出：00000000003BA0C0
	
	// 用 delete 运算符释放
	delete[] p2;
}

其中 p1 所指的 10 字节的内存空间与 p2 所指的 10 字节内存空间都是存在于堆。堆的内存地址生长方向与栈相反，由低到高，但需要注意的是，后申请的内存空间并不一定在先申请的内存空间的后面，即 p2 指向的地址并不一定大于 p1 所指向的内存地址，原因是先申请的内存空间一旦被释放，后申请的内存空间则会利用先前被释放的内存，从而导致先后分配的内存空间在地址上不存在先后关系。堆中存储的数据若未释放，则其生命周期等同于程序的生命周期。
关于堆上内存空间的分配过程，首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆节点，然后将该节点从空闲节点链表中删除，并将该节点的空间分配给程序。另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确地释放本内存空间。由于找到的堆节点的大小不一定正好等于申请的大小，系统会自动地将多余的那部分重新放入空闲链表。
1.3 堆与栈区别
堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式，主要有如下几种区别：

（1）管理方式不同。栈由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制，容易产生内存泄漏；
（2）空间大小不同。每个进程拥有的栈的大小要远远小于堆的大小。理论上，程序员可申请的堆大小为虚拟内存的大小，进程栈的大小 64bits 的 Windows 默认 1MB，64bits 的 Linux 默认 10MB；
（3）生长方向不同。堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。
（4）分配方式不同。堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由操作系统进行释放，无需我们手工实现。
（5）分配效率不同。栈由操作系统自动分配，会在硬件层级对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由C/C++提供的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。
（6）存放内容不同。栈存放的内容，函数返回地址、相关参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候，要对当前函数执行断点进行保存，需要使用栈来实现，首先入栈的是主函数下一条语句的地址，即扩展指针寄存器的内容（EIP），然后是当前栈帧的底部地址，即扩展基址指针寄存器内容（EBP），再然后是被调函数的实参等，一般情况下是按照从右向左的顺序入栈，之后是被调函数的局部变量，注意静态变量是存放在数据段或者BSS段，是不入栈的。出栈的顺序正好相反，最终栈顶指向主函数下一条语句的地址，主程序又从该地址开始执行。堆，一般情况堆顶使用一个字节的空间来存放堆的大小，而堆中具体存放内容是由程序员来填充的。
从以上可以看到，堆和栈相比，由于大量malloc()/free()或new/delete的使用，容易造成大量的内存碎片，并且可能引发用户态和核心态的切换，效率较低。栈相比于堆，在程序中应用较为广泛，最常见的是函数的调用过程由栈来实现，函数返回地址、EBP、实参和局部变量都采用栈的方式存放。虽然栈有众多的好处，但是由于和堆相比不是那么灵活，有时候分配大量的内存空间，主要还是用堆。
无论是堆还是栈，在内存使用时都要防止非法越界，越界导致的非法内存访问可能会摧毁程序的堆、栈数据，轻则导致程序运行处于不确定状态，获取不到预期结果，重则导致程序异常崩溃，这些都是我们编程时与内存打交道时应该注意的问题。
2.数据结构中的堆与栈
数据结构中，堆与栈是两个常见的数据结构，理解二者的定义、用法与区别，能够利用堆与栈解决很多实际问题。
2.1 栈简介
栈是一种运算受限的线性表，其限制是指只仅允许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），相对地，把另一端称为栈底（Bottom）。把新元素放到栈顶元素的上面，使之成为新的栈顶元素称作进栈、入栈或压栈（Push）；把栈顶元素删除，使其相邻的元素成为新的栈顶元素称作出栈或退栈（Pop）。这种受限的运算使栈拥有“先进后出”的特性（First In Last Out），简称FILO。
栈分顺序栈和链式栈两种。栈是一种线性结构，所以可以使用数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。使用数组实现的栈叫做顺序栈，使用链表实现的栈叫做链式栈，二者的区别是顺序栈中的元素地址连续，链式栈中的元素地址不连续。
栈的结构如下图所示：



栈的基本操作包括初始化、判断栈是否为空、入栈、出栈以及获取栈顶元素等。下面以顺序栈为例，使用 C++ 给出一个简单的实现。
#include<stdio.h>
#include<malloc.h>

#define DataType int
#define MAXSIZE 1024
struct SeqStack {
	DataType data[MAXSIZE];
	int top;
};

//栈初始化,成功返回栈对象指针，失败返回空指针NULL
SeqStack* initSeqStack() {
	SeqStack* s=(SeqStack*)malloc(sizeof(SeqStack));
	if(!s) {
		printf("空间不足\n");
		return NULL;
	} else {
		s->top = -1;
		return s;
	}
}

//判断栈是否为空
bool isEmptySeqStack(SeqStack* s) {
	if (s->top == -1)
		return true;
	else
		return false;
}

//入栈，返回-1失败，0成功
int pushSeqStack(SeqStack* s, DataType x) {
	if(s->top == MAXSIZE-1)
	{
		return -1;//栈满不能入栈
	} else {
		s->top++;
		s->data[s->top] = x;
		return 0;
	}
}

//出栈，返回-1失败，0成功
int popSeqStack(SeqStack* s, DataType* x) {
	if(isEmptySeqStack(s)) {
		return -1;//栈空不能出栈
	} else {
		*x = s->data[s->top];
		s->top--;
		return 0;
	}
}

//取栈顶元素，返回-1失败，0成功
int topSeqStack(SeqStack* s,DataType* x) {
	if (isEmptySeqStack(s))
		return -1;	//栈空
	else {
		*x=s->data[s->top];
		return 0;
	}
}

//打印栈中元素
int printSeqStack(SeqStack* s) {
	int i;
	printf("当前栈中的元素:\n");
	for (i = s->top; i >= 0; i--)
		printf("%4d",s->data[i]);
	printf("\n");
	return 0;
}

//test
int main() {
	SeqStack* seqStack=initSeqStack();
	if(seqStack) {
		//将4、5、7分别入栈
		pushSeqStack(seqStack,4);
		pushSeqStack(seqStack,5);
		pushSeqStack(seqStack,7);
		
		//打印栈内所有元素
		printSeqStack(seqStack);
		
		//获取栈顶元素
		DataType x=0;
		int ret=topSeqStack(seqStack,&x);
		if(0==ret) {
			printf("top element is %d\n",x);
		}
		
		//将栈顶元素出栈
		ret=popSeqStack(seqStack,&x);
		if(0==ret) {
			printf("pop top element is %d\n",x);
		}
	}
	return 0;
}

运行上面的程序，输出结果：
当前栈中的元素:
   7   5   4
top element is 7
pop top element is 7

2.2 堆简介
2.2.1 堆的性质
堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性。因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。堆的左右孩子没有大小的顺序。下面是一个小顶堆示例：



堆的存储一般都用数组来存储堆，i节点的父节点下标就为$(i – 1) / 2$。它的左右子节点下标分别为 $2 * i + 1$ 和 $2 * i + 2$。如第0个节点左右子节点下标分别为1和2。


2.2.2 堆的基本操作
（1）建立

以最小堆为例，如果以数组存储元素时，一个数组具有对应的树表示形式，但树并不满足堆的条件，需要重新排列元素，可以建立“堆化”的树。



（2）插入

将一个新元素插入到表尾，即数组末尾时，如果新构成的二叉树不满足堆的性质，需要重新排列元素，下图演示了插入15时，堆的调整。



（3）删除。

堆排序中，删除一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。表中最后一个元素用来填补空缺位置，结果树被更新以满足堆条件。


2.2.3 堆操作实现
（1）插入代码实现

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父节点到根节点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中，这就类似于直接插入排序中将一个数据并入到有序区间中，这是节点“上浮”调整。不难写出插入一个新数据时堆的调整代码：
// 新加入i节点,其父节点为(i-1)/2
// 参数：a：数组，i：新插入元素在数组中的下标  
void minHeapFixUp(int a[], int i) {  
    int j, temp;  
    temp = a[i];  
    j = (i-1)/2;      //父节点  
    while (j >= 0 && i != 0) {  
        if (a[j] <= temp)//如果父节点不大于新插入的元素，停止寻找  
            break;  
        a[i]=a[j];    		//把较大的子节点往下移动,替换它的子节点  
        i = j;  
        j = (i-1)/2;  
    }  
    a[i] = temp;  
}  

因此，插入数据到最小堆时：
// 在最小堆中加入新的数据data  
// a：数组，index：插入的下标，
void minHeapAddNumber(int a[], int index, int data) {  
    a[index] = data;  
    minHeapFixUp(a, index);  
} 

（2）删除代码实现

按照堆删除的说明，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将数组最后一个数据与根节点交换，然后再从根节点开始进行一次从上向下的调整。
调整时先在左右儿子节点中找最小的，如果父节点不大于这个最小的子节点说明不需要调整了，反之将最小的子节点换到父节点的位置。此时父节点实际上并不需要换到最小子节点的位置，因为这不是父节点的最终位置。但逻辑上父节点替换了最小的子节点，然后再考虑父节点对后面的节点的影响。堆元素的删除导致的堆调整，其整个过程就是将根节点进行“下沉”处理。下面给出代码：
// a为数组，len为节点总数；从index节点开始调整，index从0开始计算index其子节点为 2*index+1, 2*index+2；len/2-1为最后一个非叶子节点 
void minHeapFixDown(int a[],int len,int index) {
	if(index>(len/2-1))//index为叶子节点不用调整
		return;
	int tmp=a[index];
	lastIndex=index;
	while(index<=len/2-1)        //当下沉到叶子节点时，就不用调整了
	{ 
		// 如果左子节点小于待调整节点
		if(a[2*index+1]<tmp) {
			lastIndex = 2*index+1;
		}
		//如果存在右子节点且小于左子节点和待调整节点
		if(2*index+2<len && a[2*index+2]<a[2*index+1]&& a[2*index+2]<tmp) {
			lastIndex=2*index+2;
		}
		//如果左右子节点有一个小于待调整节点，选择最小子节点进行上浮
		if(lastIndex!=index) {
			a[index]=a[lastIndex];
			index=lastIndex;
		} else break;             //否则待调整节点不用下沉调整
	}
	a[lastIndex]=tmp;           //将待调整节点放到最后的位置
}

根据堆删除的下沉思想，可以有不同版本的代码实现，以上是和孙凛同学一起讨论出的一个版本，在这里感谢他的参与，读者可另行给出。个人体会，这里建议大家根据对堆调整过程的理解，写出自己的代码，切勿看示例代码去理解算法，而是理解算法思想写出代码，否则很快就会忘记。
（3）建堆

有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！先看一个数组，如下图：



很明显，对叶子节点来说，可以认为它已经是一个合法的堆了即20，60， 65， 4， 49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分别作一次向下调整操作就可以了。下图展示了这些步骤：



写出堆化数组的代码：
// 建立最小堆
// a:数组，n：数组长度
void makeMinHeap(int a[], int n) {
    for (int i = n/2-1; i >= 0; i--)  
        minHeapFixDown(a, i, n);  
}  

2.2.4 堆的具体应用——堆排序
堆排序（Heapsort）是堆的一个经典应用，有了上面对堆的了解，不难实现堆排序。由于堆也是用数组来存储的，故对数组进行堆化后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于直接选择排序。
因此，完成堆排序并没有用到前面说明的插入操作，只用到了建堆和节点向下调整的操作，堆排序的操作如下：
// array:待排序数组，len：数组长度
void heapSort(int array[],int len) {
	// 建堆
	makeMinHeap(array,len); 
	
	// 最后一个叶子节点和根节点交换，并进行堆调整，交换次数为len-1次
	for(int i=len-1;i>0;--i) {
		//最后一个叶子节点交换
		array[i]=array[i]+array[0];
		array[0]=array[i]-array[0];
		array[i]=array[i]-array[0];
        
        // 堆调整
		minHeapFixDown(array, 0, len-i-1);  
	}
}

（1）稳定性。堆排序是不稳定排序。
（2）堆排序性能分析。由于每次重新恢复堆的时间复杂度为O(logN)，共N-1次堆调整操作，再加上前面建立堆时N/2次向下调整，每次调整时间复杂度也为O(logN)。两次操作时间复杂度相加还是O(NlogN)，故堆排序的时间复杂度为O(NlogN)。
最坏情况：如果待排序数组是有序的，仍然需要O(NlogN)复杂度的比较操作，只是少了移动的操作；
最好情况：如果待排序数组是逆序的，不仅需要O(NlogN)复杂度的比较操作，而且需要O(NlogN)复杂度的交换操作，总的时间复杂度还是O(NlogN)。
因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般优于快速排序的重要一点是数据的初始分布情况对堆排序的效率没有大的影响。

参考文献
[1] 浅谈堆和栈的区别

[2] 栈内存和堆内存的区别

[3] 浅谈内存分配方式以及堆和栈的区别（很清楚）

[4] C++函数调用过程深入分析

[5] 十种排序算法
杂注
我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2z2o0f9ecoo44

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 

/*
 * 堆排序是一种选择排序，时间复杂度为O(nlog<sub>2</sub>n)。
 * 
 * 堆排序的特点是：
 * 在排序过程中，将待排序数组看成是一棵完全二叉树的顺序存储结构，
 * 利用完全二叉树中父结点和子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。
 *
 * 基本思想
 * 1.将待排序数组调整为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
 * 2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置列入有序区，然后将新的无序区调整为大根堆。
 * 3.重复操作，直到无序区消失为止。
 * 初始时，整个数组为无序区。每一次交换，都是将大根堆的堆顶元素换入有序区，以保证有序区是有序的。
 */

namespace HeapSort
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// 程序入口点。
        /// </summary>
        public static void Main()
        {
            int[] a = {1, 14, 6, 2, 8, 66, 9, 3, 0, 10, 5, 34, 76, 809, 4, 7};

            Console.WriteLine("Before Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n");

            Console.WriteLine("In Heap Sort:");
            HeapSort(a);
            Console.WriteLine("");

            Console.WriteLine("After Heap Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }
        }

        /// <summary>
        /// 堆排序方法。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        private static void HeapSort(int[] a)
        {
            // 建立大根堆。
            BuildMaxHeap(a);
            Console.WriteLine("Build max heap:");
            foreach (int i in a)
            {
                // 打印大根堆。
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\nMax heap in each heap sort iteration:");
            for (int i = a.Length - 1; i > 0; i--)
            {
                // 将堆顶元素和无序区的最后一个元素交换。
                Swap(ref a[0], ref a[i]);

                // 将新的无序区调整为大根堆。
                MaxHeaping(a, 0, i);

                // 打印每一次堆排序迭代后的大根堆。
                for (int j = 0; j < i; j++)
                {
                    Console.Write(a[j] + " ");
                }

                Console.WriteLine(string.Empty);
            }
        }

        /// <summary>
        /// 由底向上建堆。
        /// 由完全二叉树的性质可知，叶子结点是从index=a.Length/2开始，
        /// 所以从index=(a.Length/2)-1结点开始由底向上进行大根堆的调整。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        private static void BuildMaxHeap(int[] a)
        {
            for (int i = (a.Length / 2) - 1; i >= 0; i--)
            {
                MaxHeaping(a, i, a.Length);
            }
        }

        /// <summary>
        /// 将指定的结点调整为堆。
        /// </summary>
        /// <param name="a">
        /// 待排序数组。
        /// </param>
        /// <param name="i">
        /// 需要调整的结点。
        /// </param>
        /// <param name="heapSize">
        /// 堆的大小，也指数组中无序区的长度。
        /// </param>
        private static void MaxHeaping(int[] a, int i, int heapSize)
        {
            // 左子结点。
            int left = (2 * i) + 1;

            // 右子结点。
            int right = 2 * (i + 1);

            // 临时变量，存放大的结点值。
            int large = i;

            // 比较左子结点。
            if (left < heapSize && a[left] > a[large])
            {
                large = left;
            }

            // 比较右子结点。
            if (right < heapSize && a[right] > a[large])
            {
                large = right;
            }

            // 如有子结点大于自身就交换，使大的元素上移；并且把该大的元素调整为堆以保证堆的性质。
            if (i != large)
            {
                Swap(ref a[i], ref a[large]);
                MaxHeaping(a, large, heapSize);
            }
        }

        /// <summary>
        /// 交换两个整数的值。
        /// </summary>
        /// <param name="a">整数a。</param>
        /// <param name="b">整数b。</param>
        private static void Swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
    }
}

// Output:
/*
Before Heap Sort:
1 14 6 2 8 66 9 3 0 10 5 34 76 809 4 7

In Heap Sort:
Build max heap:
809 14 76 7 10 66 9 3 0 8 5 34 1 6 4 2
Max heap in each heap sort iteration:
76 14 66 7 10 34 9 3 0 8 5 2 1 6 4
66 14 34 7 10 4 9 3 0 8 5 2 1 6
34 14 9 7 10 4 6 3 0 8 5 2 1
14 10 9 7 8 4 6 3 0 1 5 2
10 8 9 7 5 4 6 3 0 1 2
9 8 6 7 5 4 2 3 0 1
8 7 6 3 5 4 2 1 0
7 5 6 3 0 4 2 1
6 5 4 3 0 1 2
5 3 4 2 0 1
4 3 1 2 0
3 2 1 0
2 0 1
1 0
0

After Heap Sort:
0 1 2 3 4 5 6 7 8 9 10 14 34 66 76 809
*/