數據結構什麼是堆

1. 數據結構中堆的定義是

堆(Heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵完全二叉樹的數組對象。

堆總是滿足下列性質：

1.堆中某個節點的值總是不大於或不小於其父節點的值；

2、堆總是一棵完全二叉樹。

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。堆是非線性數據結構，相當於一維數組，有兩個直接後繼。

(1)數據結構什麼是堆擴展閱讀：

操作實現

在程序中，堆用於動態分配和釋放程序所使用的對象。在以下情況中調用堆操作：

1、事先不知道程序所需對象的數量和大小。

2、對象太大，不適合使用堆棧分配器。

堆使用運行期間分配給代碼和堆棧以外的部分內存。

傳統上，操作系統和運行時庫隨附了堆實現。當進程開始時，操作系統創建稱為進程堆的默認堆。如果沒有使用其他堆，則使用進程堆分配塊。語言運行時庫也可在一個進程內創建單獨的堆。

當應用程序或DLL創建專用堆時，這些堆駐留於進程空間中並且在進程范圍內是可訪問的。某一給定堆分配的任何數據應為同一堆所釋放。（從一個堆分配並釋放給另一個堆沒有意義。）

2. 急！！！數據結構中什麼是堆清舉例說明。

堆棧
在計算機領域，堆棧是一個不容忽視的概念，但是很多人甚至是計算機專業的人也沒有明確堆棧其實是兩種數據結構。

要點：

堆：順序隨意

棧：先進後出

堆和棧的區別

一、預備知識—程序的內存分配

一個由c/C++編譯的程序佔用的內存分為以下幾個部分

1、棧區（stack）— 由編譯器自動分配釋放 ，存放函數的參數值，局部變數的值等。其操作方式類似於數據結構中的棧。

2、堆區（heap） — 一般由程序員分配釋放， 若程序員不釋放，程序結束時可能由OS回收 。注意它與數據結構中的堆是兩回事，分配方式倒是類似於鏈表，呵呵。

3、全局區（靜態區）（static）—，全局變數和靜態變數的存儲是放在一塊的，初始化的全局變數和靜態變數在一塊區域， 未初始化的全局變數和未初始化的靜態變數在相鄰的另一塊區域。 - 程序結束後有系統釋放

4、文字常量區 —常量字元串就是放在這里的。 程序結束後由系統釋放

5、程序代碼區—存放函數體的二進制代碼。

二、例子程序

這是一個前輩寫的，非常詳細

//main.cpp

int a = 0; 全局初始化區

char *p1; 全局未初始化區

main()

{

int b; 棧

char s[] = "abc"; 棧

char *p2; 棧

char *p3 = "123456"; 123456在常量區，p3在棧上。

static int c =0； 全局（靜態）初始化區

p1 = (char *)malloc(10);

p2 = (char *)malloc(20);

分配得來得10和20位元組的區域就在堆區。

strcpy(p1, "123456"); 123456放在常量區，編譯器可能會將它與p3所指向的"123456"優化成一個地方。

}

二、堆和棧的理論知識

2.1申請方式

stack:

由系統自動分配。 例如，聲明在函數中一個局部變數 int b; 系統自動在棧中為b開辟空間

heap:

需要程序員自己申請，並指明大小，在c中malloc函數

如p1 = (char *)malloc(10);

在C++中用new運算符

如p2 = (char *)malloc(10);

但是注意p1、p2本身是在棧中的。

2.2

申請後系統的響應

棧：只要棧的剩餘空間大於所申請空間，系統將為程序提供內存，否則將報異常提示棧溢出。

堆：首先應該知道操作系統有一個記錄空閑內存地址的鏈表，當系統收到程序的申請時，

會遍歷該鏈表，尋找第一個空間大於所申請空間的堆結點，然後將該結點從空閑結點鏈表中刪除，並將該結點的空間分配給程序，另外，對於大多數系統，會在這塊內存空間中的首地址處記錄本次分配的大小，這樣，代碼中的delete語句才能正確的釋放本內存空間。另外，由於找到的堆結點的大小不一定正好等於申請的大小，系統會自動的將多餘的那部分重新放入空閑鏈表中。

2.3申請大小的限制

棧：在Windows下,棧是向低地址擴展的數據結構，是一塊連續的內存的區域。這句話的意思是棧頂的地址和棧的最大容量是系統預先規定好的，在 WINDOWS下，棧的大小是2M（也有的說是1M，總之是一個編譯時就確定的常數），如果申請的空間超過棧的剩餘空間時，將提示overflow。因此，能從棧獲得的空間較小。

堆：堆是向高地址擴展的數據結構，是不連續的內存區域。這是由於系統是用鏈表來存儲的空閑內存地址的，自然是不連續的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限於計算機系統中有效的虛擬內存。由此可見，堆獲得的空間比較靈活，也比較大。

2.4申請效率的比較：

棧由系統自動分配，速度較快。但程序員是無法控制的。

堆是由new分配的內存，一般速度比較慢，而且容易產生內存碎片,不過用起來最方便.

另外，在WINDOWS下，最好的方式是用VirtualAlloc分配內存，他不是在堆，也不是在棧是直接在進程的地址空間中保留一快內存，雖然用起來最不方便。但是速度快，也最靈活

2.5堆和棧中的存儲內容

棧： 在函數調用時，第一個進棧的是主函數中後的下一條指令（函數調用語句的下一條可執行語句）的地址，然後是函數的各個參數，在大多數的C編譯器中，參數是由右往左入棧的，然後是函數中的局部變數。注意靜態變數是不入棧的。

當本次函數調用結束後，局部變數先出棧，然後是參數，最後棧頂指針指向最開始存的地址，也就是主函數中的下一條指令，程序由該點繼續運行。

堆：一般是在堆的頭部用一個位元組存放堆的大小。堆中的具體內容有程序員安排。

2.6存取效率的比較

char s1[] = "aaaaaaaaaaaaaaa";

char *s2 = "bbbbbbbbbbbbbbbbb";

aaaaaaaaaaa是在運行時刻賦值的；

而bbbbbbbbbbb是在編譯時就確定的；

但是，在以後的存取中，在棧上的數組比指針所指向的字元串(例如堆)快。

比如：

#include

void main()

{

char a = 1;

char c[] = "1234567890";

char *p ="1234567890";

a = c[1];

a = p[1];

return;

}

對應的匯編代碼

10: a = c[1];

00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]

0040106A 88 4D FC mov byte ptr [ebp-4],cl

11: a = p[1];

0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]

00401070 8A 42 01 mov al,byte ptr [edx+1]

00401073 88 45 FC mov byte ptr [ebp-4],al

第一種在讀取時直接就把字元串中的元素讀到寄存器cl中，而第二種則要先把指針值讀到edx中，在根據edx讀取字元，顯然慢了。

?

2.7小結：

堆和棧的區別可以用如下的比喻來看出：

使用棧就象我們去飯館里吃飯，只管點菜（發出申請）、付錢、和吃（使用），吃飽了就走，不必理會切菜、洗菜等准備工作和洗碗、刷鍋等掃尾工作，他的好處是快捷，但是自由度小。

使用堆就象是自己動手做喜歡吃的菜餚，比較麻煩，但是比較符合自己的口味，而且自由度大。

堆和棧的區別主要分：

操作系統方面的堆和棧，如上面說的那些，不多說了。

還有就是數據結構方面的堆和棧，這些都是不同的概念。這里的堆實際上指的就是（滿足堆性質的）優先隊列的一種數據結構，第1個元素有最高的優先權；棧實際上就是滿足先進後出的性質的數學或數據結構。

雖然堆棧，堆棧的說法是連起來叫，但是他們還是有很大區別的，連著叫只是由於歷史的原因。

3. 數據結構-堆

堆其實就是一棵完全二叉樹，即若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊。

定義為：具有n個元素的序列（h1,h2,...hn），當且僅當滿足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)時稱之為堆。完全二叉樹的根結點稱為堆的頂。

可以注意到，堆僅保證元素和其子結點之間的關系，並不保證兄弟結點之間的關系。

常見的堆包括最大堆和最小堆。

最大堆，顧名思義，堆頂的鍵值是所有堆結點鍵值中最大者。套用前面講到過的規則， 當且僅當滿足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2) ，所有父結點的鍵值均大於子結點。

由最大堆的定義，可以很容易的理解最小堆，即所有父結點的鍵值均小於子結點。

堆的內存形式有兩種，一種是鏈表，一種是數組。

對於一個堆，常用的操作有兩種，插入一個新的結點和刪除堆頂。

向堆插入一個結點，首先要保證堆依然是一個完全二叉樹，即必須保證一行（也就是一層）構建完成才能繼續添加下一層的結點。這就意味著完全二叉樹新增加結點的位置是唯一固定的。對應數組來說，就是在數組的末尾增加一個元素。

進一步，對這個完全二叉樹進行調整，即移動父結點和子結點的相互位置關系，使其滿足條件而重新成為堆。這種調整可以簡單的看成是一些列的上浮（shift-up）操作。可以看看下面這個簡單的圖。

可以看到，所謂的shift-up，就是將新插入的結點不停的和其父結點進行比較，如果子結點的鍵值大於（最大堆）/小於（最小堆）其父結點，那麼就對二者進行交換，因為這里是數組，所以僅需要交換結點之間的鍵值，直到子結點的鍵值不大於（最大堆）/不小於（最小堆）其父結點。

和插入新的結點類似，刪除堆頂，還是首先要保證堆依然是一個完全二叉樹，即必須保證一行（也就是一層）全部刪除之後才能繼續刪除上一層的結點。這就意味著完全二叉樹刪除的結點的位置是唯一固定的。對應數組來說，就是刪除數組末尾的元素。

刪除堆頂的操作可以分為3步：

步驟1和2非常簡單，執行完成之後，新的完全二叉樹如圖所示：

步驟3是問題的重點和難點，可以簡單的看成是一些列的下沉（shift-down）操作。

對於某個結點（parent），所謂的shift-down，包括以下子步驟（這里以最大堆為例）：

以上面的堆為例：

構建堆有兩種方式，一種是從無到有，也就是一個不斷插入結點的過程；而另一種就是在原有完全二叉樹的基礎上，按照某種規則對結點進行調整。

從原理上說，從無到有的構建堆比較簡單，對於每一個新增結點，對其進行插入操作，結果必然是一個堆。

在原有的完全二叉樹上進行調整，稍微復雜一些，可以從最後一個非葉結點開始，對每個非葉結點進行shift-down操作。

該操作的難點在於如何找到「非葉結點」和「最後一個非葉結點」。考慮非葉結點的定義，一個結點如果 有至少一個子結點 ，那麼就稱其為 非葉結點 。因此，我們只要遍歷所有的結點（根結點除外）的父結點，就可以遍歷所有的 非葉結點 。知道了如何找到「非葉結點」，找出「最後一個非葉結點」的方法顯而易見，最後一個葉結點（數組的末尾）的父結點就是「最後一個非葉結點」。

通過之前的章節，不難看出，堆操作的核心是兩個步驟：shift-down和shift-up，更進一步，這兩個操作都是遞歸的。

不僅在面試中，堆在日常工作中也經常被使用。堆經常會被作為優先隊列來使用，常見於例如任務調度，數組合並等場景。

在java中，優先隊列實現了堆的數據結構【1】。我之前的一篇文章 Java 優先隊列 （PriorityQueue） 對優先隊列進行了簡單介紹，可以參考。
【1】 https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

其他參考文章：
【2】 最大堆（創建、刪除、插入和堆排序）
【3】 數據結構：堆（Heap）
【4】 關於堆結構的詳解
【5】 構建堆的時間復雜度
【6】 最大堆的插入/刪除/調整/排序操作(圖解+程序)（JAVA）

4. 什麼是堆

堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：

1 堆中某個節點的值總是不大於或不小於其父節點的值；

2 堆總是一棵完全二叉樹。

將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。

(4)數據結構什麼是堆擴展閱讀

堆的實現通過構造二叉堆（binary heap），實為二叉樹的一種；由於其應用的普遍性，當不加限定時，均指該數據結構的這種實現。這種數據結構具有以下性質。任意節點小於（或大於）它的所有後裔，最小元（或最大元）在堆的根上（堆序性）。

堆總是一棵完全樹。即除了最底層，其他層的節點都被元素填滿，且最底層盡可能地從左到右填入。

堆棧的基本特點：先入後出，後入先出。除頭尾節點之外。

5. 數據結構-堆和棧的簡單理解

堆是一種常用的樹形結構，是一種特殊的完全二叉樹，當且僅當滿足所有節點的值總是不大於或不小於其父節點的值的完全二叉樹被稱之為堆。堆的這一特性稱之為 堆序性 。因此，在一個堆中，根節點是最大（或最小）節點。如果根節點最小，稱之為小頂堆（或小根堆），如果根節點最大，稱之為大頂堆（或大根堆）。

堆的操作有：建立，插入和刪除。

6. 數據結構中,什麼是堆

堆是一種特殊的樹形數據結構，每個結點都有一個值。通常我們所說的堆的數據結構，是指二叉堆。堆的特點是根結點的值最小（或最大），且根結點的兩個子樹也是一個堆
堆分為大根堆,小根堆,大根堆就是樹的根結點大於葉子結點.

7. 什麼是堆，什麼是棧，什麼是堆棧

堆和棧是兩個很廣泛的概念，在多個領域有使用。
1.內存中的堆和棧:
變數都存放在內存中，內存給變數開辟了兩塊區域,分別為棧區域和堆區域
基本數據類型都存放在棧區域
引用數據類型都存放在堆區域

棧的特點,開口向上,速度快,容量小
堆的特點,速度稍慢,容量比較大

2.數據結構中的堆和棧：
堆：順序隨意
棧：後進先出(Last-In/First-Out)
https://www.cnblogs.com/guoxiaoyan/p/8664150.html

3.java的集合框架中還有一種叫做 Stack（堆棧）的集合，是一種先進後出的數據結構

3種棧都有共同的特點：先進後出

堆內存與數據結構堆沒關系

有一個相關的名稱叫堆棧，其實指的是棧。

end

8. 數據結構裡面堆是什麼東西堆是跟二叉樹有什麼關系

簡單說堆是一種完全二叉樹 一般總用來構造優先順序隊列
堆的特性是父結點總優它任意子節點(所以堆頂元素為最優 但不需要保證左子樹和右子樹的關系)

堆的物理結構一般用數組等支持索引的線性結構(因為是完全二叉樹..)
並且實現構造堆 彈出堆頂元素 添加元素並調整堆等操作

堆排序也是用這個原理實現的 先構造一個堆 然後不斷的彈出堆頂元素並調整堆 生成的序列則是有序的

9. 什麼是堆什麼是棧啊

堆（英語：heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。

棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。

向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

(9)數據結構什麼是堆擴展閱讀：

一、堆的演算法思想

不必將值一個個地插入堆中，通過交換形成堆。假設根的左、右子樹都已是堆，並且根的元素名為R。這種情況下，有兩種可能：

（1） R的值小於或等於其兩個子女，此時堆已完成。

（2） R的值大於其某一個或全部兩個子女的值，此時R應與兩個子女中值較小的一個交換，結果得到一個堆，除非R仍然大於其新子女的一個或全部的兩個。這種情況下，我們只需簡單地繼續這種將R「拉下來」的過程，直至到達某一個層使它小於它的子女，或者它成了葉結點。

二、棧的基本演算法

1、進棧（PUSH）演算法

①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）。

②置TOP=TOP+1（棧指針加1，指向進棧地址）。

③S(TOP)=X，結束（X為新進棧的元素）。

2、退棧（POP）演算法

①若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)。

②X=S(TOP)，（退棧後的元素賦給X）。

③TOP=TOP-1，結束（棧指針減1，指向棧頂）。