heap堆其實是一種比較復雜的數據結構,尤其涉及到建堆和調整堆的時候。好在在STL中已經封裝了heap的一些操作,可以讓我們比較方便的使用堆。比如判斷堆,刪除一個元素,插入一個元素,以及堆排序。示例代碼上傳至 https://github.com/chenyufeng1991/STL_heap。
(1)首先導入頭文件.
(2)這裡使用數組來存儲一個堆,也就是堆化數組,為了方便使用,我把數組轉化為vector來操作。
int arr[] = {4,5,6,7,8,1}; vector(3)is_heap:判斷堆vectorArr(arr,arr + sizeof(arr) / sizeof(int));
cout <<"-"<此時輸出肯定為false;
(4)make_heap:構造堆// 構造最大堆 make_heap(vectorArr.begin(), vectorArr.end(), less()); cout <<"_ _"< 注意make_heap的第三個參數中,less ()為構造最大堆,greater ()為構造最小堆。此時判斷is_heap即為true; (5)push_heap:插入元素
// 向堆中插入一個元素,默認插入在頂部 vectorArr.push_back(100); cout << "_ _ _"<如果要在堆中插入一個元素,首先要往容器vector尾部中插入該元素,然後再使用push_heap調整堆。 (6)pop_heap:彈出元素
// 彈出一個元素,默認是首元素和尾元素交換,交換以後就不是正確的堆了;真正的刪除需要去vector裡面pop; pop_heap(vectorArr.begin(), vectorArr.end()); cout <<"_ _ _ _ _"<彈出的元素默認的是根節點的元素,然後在用尾元素放到根節點處,然後再調整。 pop_heap之後並沒有真正刪除該元素,最後是使用容器pop_back來刪除的。 (7)sort_heap:堆排序
// 堆排序, 堆排序後 sort_heap(vectorArr.begin(), vectorArr.end()); cout <<"_ _ _ _ _ _ _"<堆排序後不是一個真正的堆了,只是完成了排序。