LintCode 堆化詳解及實(shí)例代碼
LintCode 堆化詳解及實(shí)例代碼
給出一個(gè)整數(shù)數(shù)組，堆化操作就是把它變成一個(gè)最小堆數(shù)組。
對(duì)于堆數(shù)組A，A[0]是堆的根，并對(duì)于每個(gè)A[i]，A [i * 2 + 1]是A[i]的左兒子并且A[i * 2 + 2]是A[i]的右兒子。
樣例
給出 [3,2,1,4,5]，返回[1,2,3,4,5] 或者任何一個(gè)合法的堆數(shù)組
挑戰(zhàn)
O(n)的時(shí)間復(fù)雜度完成堆化
說(shuō)明
什么是堆？
堆是一種數(shù)據(jù)結(jié)構(gòu)，它通常有三種方法：push， pop 和 top。其中，“push”添加新的元素進(jìn)入堆，“pop”刪除堆中最小/最大元素，“top”返回堆中最小/最大元素。
什么是堆化？
把一個(gè)無(wú)序整數(shù)數(shù)組變成一個(gè)堆數(shù)組。如果是最小堆，每個(gè)元素A[i]，我們將得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]
如果有很多種堆化的結(jié)果？
返回其中任何一個(gè)。
分析：一開(kāi)始想到堆化么肯定就是堆排序吧，粗粗一想貌似復(fù)雜度是O(nlgn)，后來(lái)參考該文章才知道O(nlgn)是復(fù)雜度上限，平均是O(n)
代碼：
class Solution {
public:
/**
* @param A: Given an integer array
* @return: void
*/
void heapify(vector<int> &A) {
// write your code here
int n = A.size()-1;
for(int i=n/2;i>=0;i--)
heapify(A,i);
}
void heapify(vector<int> &A,int i)
{
int l = 2*i+1;
int r = 2*i+2;
int smallest = i;
if(l<A.size()&&A[l]<A[smallest])
smallest = l;
if(r<A.size()&&A[r]<A[smallest])
smallest = r;
if(smallest!=i)
{
swap(A[i],A[smallest]);
heapify(A,smallest);
}
}
};
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)字符串分割的實(shí)例
這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)字符串分割的實(shí)例的相關(guān)資料,希望通過(guò)本文能幫助到大家實(shí)現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10
本篇文章主要介紹了C語(yǔ)言WinSock學(xué)習(xí)筆記，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2007-12-12
C語(yǔ)言實(shí)現(xiàn)紙牌24點(diǎn)小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)紙牌24點(diǎn)小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
C++模擬實(shí)現(xiàn)string的詳細(xì)過(guò)程
在?C++?編程中,字符串的處理是一項(xiàng)常見(jiàn)且重要的任務(wù),標(biāo)準(zhǔn)庫(kù)中的?string?類為我們提供了便捷、高效的字符串操作方法,模擬實(shí)現(xiàn)?string?類?的背景源于對(duì)?C++?底層原理的探索欲望,所以本文給大家介紹了C++模擬實(shí)現(xiàn)string的詳細(xì)過(guò)程,需要的朋友可以參考下2024-08-08
C++11 線程同步接口std::condition_variable和std::future的簡(jiǎn)單使用示例詳
本文介紹了std::condition_variable和std::future在C++中的應(yīng)用,用于線程間的同步和異步執(zhí)行,通過(guò)示例代碼,展示了如何使用std::condition_variable的wait和notify接口進(jìn)行線程間同步2024-09-09
C語(yǔ)言實(shí)現(xiàn)文件讀寫操作的幾種常用方法
C語(yǔ)言提供了一系列文件操作函數(shù),使得我們可以通過(guò)程序?qū)ξ募M(jìn)行讀寫操作,本文主要介紹了C語(yǔ)言實(shí)現(xiàn)文件讀寫操作的幾種常用方法,具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03
自C++17起就通過(guò)使用類模板參數(shù)推導(dǎo),只要編譯器能根據(jù)初始值推導(dǎo)出所有模板參數(shù),那么就可以不指明參數(shù),下面我們就來(lái)看看C++17中類模板參數(shù)推導(dǎo)的具體使用吧2024-03-03
這篇文章主要為大家詳細(xì)介紹了opencv實(shí)現(xiàn)顏色檢測(cè)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-04-04
詳解C語(yǔ)言常用的一些轉(zhuǎn)換工具函數(shù)
這篇文章主要介紹了C語(yǔ)言常用的一些轉(zhuǎn)換工具函數(shù),本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-11-11
本篇文章是對(duì)C++中的Data Member內(nèi)存布局進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-07-07