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