Heap （堆） — wdv4758h-notes latest 說明文件

Heap 常被作為Priority Queue （一種Abstract Data Type）的實作方式。

而一個Heap 常見的實作為Binary Heap，它的樹為Complete Binary Tree。

Heap 在一些圖論的演算 ... wdv4758h-notes latest 演算法與資料結構 ADT(AbstractDataType) 演算法相關概念 BigONotation Books Cache CacheFriendlyAlgorithms Dict Heap（堆） Heap基本介紹 常見操作 BinaryHeap BinomialHeap FibonacciHeap 實作 實作概況 BinaryHeap Rust Python 參考 演算法與資料結構 InverseSquareRoot Misc ProbabilisticDataStructure RandomNumberGenerator 演算法 SubstringSearching Android AndroidEmulator AndroidImages Anbox-在GNU/Linux上執行Android系統 AndroidApps Android’sBinder Androidboot AndroidCheatSheet AndroidProcessCrashDebug AndroidCTS(CompatibilityTestSuite) GoogleProjectButter 硬體抽象層(HAL)(HardwareAbstractionLayer) Android-init 安裝新Android AndroidKernel libhybris LinuxenvironmentonAndroid AndroidNDK 移植到新硬體(PortingtonewHardware) AndroidProfiling 重刷Android版子 SurfaceFlinger ARMServer ARMIntroduction Python-NeedForSpeed 用TravisCI自動化發佈reStructuredText到GitHubPages上 CPU&ISA AssemblyCheatSheet SHAExtensions libuv BinaryInstrumentation Reference Blog ArtificialNeuralNetwork History Reference Installation CrossCompile Control PerformanceTesting Reference C++繼承 VirutalFunction C++11-override&final Ref BasicLinuxIPC D-Bus kdbus WebStorageV.S.Cookies WebStorage Reference bzImage initramfs zlib LinuxStandardBase(LSB) FilesystemHierarchyStandard(FHS) Stack&Heap CommonMemoryProblem Debugger RAII(ResourceAcquisitionIsInitialization) Ownership GarbageCollection Cases AllocatorImplementations DebuggingDataFormat Reference Install Linux MacOSX Browser Introduction Reference Introduction Tutorial 額外紀錄 Reference Introduction HelloWorld PyStone PyBench2.0 Richards 總結 Reference Introduction Tutorial Celerywithnon-Python FrequentlyAskedQuestions Reference ch14-1-functionalprogramming ch14-4RubywithC ch14-5OpenSource ch2-5DuckTyping ch8RegularExpression ch9-1Integer ch9-2Float InstallQEMU CreateImage InstallOSfrombootableISO QEMUwithKVM Syntax Closure和外部變數 「move」closures Closureimplementation closuresasarguments returningclosures Reference Solution1 Solution2 Solution3 Solution4 Todo Intro. Ch5-BoundaryValueTesting Ch6-EquivalenceClassTesting Ch7-DecisionTable-basedTesting Ch8-PathTesting Ch9-DataFlowTesting Ref [Ｏ]BigNumber支援？ [Ｏ]First-classfunction支援？ [Ｏ]map/reduce/filter之類的東西？ [Ｏ]Optiontype(maybetype)? [Ｏ]OOP(object-orientedprogramming)？ [Ｏ]TypeInference [Ｏ]高度的MemoryControl？ [－]REPL？ [？]預設提供的SortAlgorithm是啥？ [Ｏ]RegularExpression支援？ [Ｏ]FFI(ForeignFunctionInterface)？ [Ｏ]Importthirdpartylibrary？ [Ｏ]NativeThreadingSupport？ [Ｘ]GarbageCollection？ [Ｏ]FormatString？ [Ｏ]Ownership？ ThirdParty vdpau libva Chromium Reference 方法1:在insertmode快速貼上 方法2:在normalmode快速貼上 其他應用-從Vim裡複製到systemclipboard 其他Vimregisters 參考資料 libinput 近況 Users Reference 瀏覽器相關 CDM Chrome CSS HowBrowserWork WebExtensions Firefox Firefox設定 HTML Issues 隱私和個資 ServiceWorker Servo WebAssembly BuildSystem CMake GYP Makefile Meson C C CCheatSheet ExceptionsinC SomeC’sfeatures GLib GNUExtension InternalandExternalLinkageinC mmap pragmaonce pragmaweak 相關資源 UndefinedBehavior 256color CLI/TUI工具 autossh Bash BasicSystemUtils BusyBox-人人都該備一個在身邊的執行檔 晶片讀卡機 curl date du file-檢查檔案種類 find hwclock InputMethod Installer SomeBasicTools IRC xmodmap setxkbmap lsblk-顯示裝置資訊 Office RemoteDesktop rsync sed Shell SSHConfig sudo Sway tar test指令 timedatectl Tips Tmux 工具 xargs 雲端服務(CloudService) 編譯器 CompilerAutotuning BranchPredictionHint ClangOptions ClangTools CodeGeneration CompilerandLearning CompilerOptions LLVM-compiler-rt Computedgoto CrossCompile crt Environment GCCPlugins GPGPU IncrementalCompilation 編譯器 JumpThreading Legalization LLVM AndroidWithLLVM LLVM&CUDA LLVM輔助測試 LLVMIR LLVM&Python LLVMtoVHDL/Verilog NameMangling Obfuscator Objdump UseCompilerToHelpPorting CompilerResource SSA StreamingCompilation Talks TCGIR-TinyCodeGenerator 轉譯器(Transpiler)(Source-to-SourceCompiler) 壓縮 壓縮入門 JPEGCompression PNGCompression 資料壓縮相關資源 電腦視覺(ComputerVision) SIFT BackgroundSubtraction 電腦視覺相關書籍 ImageSegmentation ObjectDetection ObjectRecognition ObjectTracking Panorama(ImageStitching) SuperResolution VideoTracking VisualQuestionAnswering Concurrency Lock 名詞釐清 Container chroot Docker FreeBSDJail LinuxContainers(LXC) CI(ContinouseIntegration) Buildbot ContinuousIntegration Concourse Drone Jenkins TravisCI WorkflowPipeline 64BitsProblem C++ SFINAE(SubstitutionFailureIsNotAnError) std::array C++&Assembly C++BitField C++17 C++Concepts C++const CopyElision C++Coroutine C++CoreGuidelines CRTP(CuriouslyRecurringTemplatePattern) C++Constructors&Destructors DesignPattern C++Documentation Experimental explicitspecifier ExpressionTemplates ForwardDeclaration C++History 繼承(Inheritance) Initialization lambdafunction Macro C++Misc C++Optimizations Optional C++-Parallel PerfectForwarding Pimpl Qt C++REPL C++Resource RVO(ReturnValueOptimization) Aboutsize_tandptrdiff_t SmartPointer StandardLibraryImplementation static C++STL StringOptimization TemporaryObjects C++Testing C++Thread Todo 型別轉換(TypeConversion) 型別推斷(TypeDeduction) C++ValueCategory C++Videos CPU&ISA AssemblyCheatSheet SHAExtensions Blowfish EllipticCurve Crypto SHA(SecureHashAlgorithm) 資料庫(Database) CockroachDB RaftConsensusAlgorithm LevelDB MariaDB MongoDB MySQL Database Redis Database(資料庫) SQL(StructuredQueryLanguage) SQLite TiDB 除錯相關(Debugging) FlameScope GDB DebuggerforJavaScript DebuggingaKernel PDB-PythonDebugger Resource rr-recordandreplayframework strace 文件(Documentation) LaTeX教學 reStructuredText Sphinx E-Book EPUB 編輯器 Emacs 嵌入式(Embedded) BSP(BoardSupportPackage) FPGA EmbeddedResource STM32 字型相關(Fonts) 形式驗證(FormalVerification) 朋友的筆記 遊戲(Game) Emulators 遊戲引擎(GameEngine) Real-timeStrategyGames GamesResource Roguelike Role-playingGames(RPG) 守塔(TowerDefense) WindowsGameonLinux ArrayFire Boost.Compute GPGPUwithKernel SPIR-V 圖像處理(Graphics) Cairo-跨平台二維向量繪圖 DRI(DirectRenderingInfrastructure) GLSL-OpenGLShadingLanguage Graphic LinuxGraphics Mesa-跨平台三維繪圖 OpenGL GraphicResource VirtualGL Vulkan GUI GTK Qt 硬體相關(Hardware) Hardware&Programming 耳機(Headphone) Hardware’sHistory Kindle Resource RISC-V 相關資源 機器學習(MachineLearning) CheatSheet 數學相關 計算機 誤差 數學相關套件(MathLibraries) 線性代數（LinearAlgebra） MathonWeb Math W^X(WriteXORExecute) Allocator AddressSanitizerAlgorithm KernelMemoryManagement Memory MemoryAllocator-UnderTheHood MemoryHardware MemoryManagement MemoryProfiler MemoryProfiling Sanitizer StackProtection AdvertisementBlocker Archive 一些閱讀過的文章 頻寬成本 BioDataFormat BitHacks 踩Bug紀錄(從2015-10-26開始) CAD(Computer-AidedDesign) Calendar ChatOps CloudMessage Conference OpenSource專案貢獻 DiskEncryption DOTLanguage 簡易網站建立服務 EsotericProgrammingLanguage FishShell FloatingPoint Forum 臺灣自由軟體界 FunnySites GoogleOnHub 十六進位浮點數（HexFloat） Hexspeak HighAvailability 資訊相關歷史 HostBlocker HTTPHistory Images 物聯網(IoT)(InternetofThings) IRC Jargons Keyboard LinuxFoundation LogAnalysis MailSystem ManPage Misc Netflix OpenAPI OpenHouse OpenSourcePorjectsILove 緣由 Papers PDFViewerHistory 效能要點(Performance) Podcast ProjectMeasurement proxychains 資訊相關書籍出版社 遠端工作(RemoteJobs) InterestingRepo 資源來源 逆向工程 火箭 SAT/SMTSolver SelfHosting Sites SoftwareUpdates Statifier 台灣軟體界 TaskExecutionFramework TaskSchedule TeamCollaboration Todo 想做的專案 Tools TraceCode 翻譯(Translation) 技術屁話 TuringComplete Typesetting 大學修過的課程 Unicode解說 Video 一些Talk的影片 VoiceSimulation WindowsBatch WorkingMemory 多媒體(Multimedia) Audio 基本概念 GStreamer Kodi-OpenSourceHomeTheaterSoftware LinuxSoundSystem MediaContainer MediaInfo MIDI MusicPlayer OpenCV PipeWire 播放器 PTS/DTS(PresentationTimeStamp/DecodeTimeStamp) PulseAudio SDP(SessionDescriptionProtocol) Video VideoQuality 網路相關(Network) AMQP(AdvancedMessageQueuingProtocol) C10K C10M DDoS Distributed DNS DTLS(DatagramTransportLayerSecurity) HTTP(HypertextTransferProtocol) ICE(InteractiveConnectivityEstablishment) iperf-TCP/UDP/SCTP網路效能測量 Microservice NetworkMonitoring MQTT(MessageQueuingTelemetryTransport) nanomsg NetworkLoadBalancer NetworkStack Nginx OSsocketbuffer Proxy QUIC 資源 RPC 安全性檢查 SRT(SecureReliableTransport) TCP tcpdump UDP UPnP VPN WebSocket WebTorrent 作業系統 作業系統相關歷史 OpenHMPP OpenMP Parallel 平行化相關資源 程式語言(ProgrammingLanguage) InterpreterForCompiledLanguage 語言效能比較 Python PythonAST Python-async&await Asynchronous Benchmark BestPractice PythonCompiler Python’sConcurrency contextlib CPython CPythonEquality CPythonExtension Cython Debugger SomeDeprecatedThings Django CPythonGIL(GlobalInterpreterLock) Python&Hardware Python-InstallPackages Python Iterator Kivy-PythononAndroid Linter&Formatter 製作Packages matplotlib Nuitka Numpy Operator SomePackages ParserinPython 遷移至Python3 **operatorv.s.math.pow PyPI PyPy Python3.5 Python3.6 Python3.7 Qt Resource SciPy StandardLibrary SymPy PythonTesting PythonTips virtualenv yieldwithlistcomprehension 量子電腦 RE2-fast,safe,thread-friendlyalternativetobacktrackingregularexpressionengines RegularExpression RegularExpressionLibrary Resource EngineeringReport-Week28,2015 EngineeringReport-Week29,2015 EngineeringReport-Week30,2015 EngineeringReport-Week31,2015 EngineeringReport-Week32,2015 EngineeringReport-Week33,2015 EngineeringReport-Week34,2015 EngineeringReport-Week35,2015 EngineeringReport-Week36,2015 EngineeringReport-Week37,2015 SelfReport-Week53,2015 SelfReport-Week54,2015 SelfReport-Week55,2015 SelfReport-Week56,2015 SelfReport-Week19,2016 SelfReport-Week20,2016 SelfReport-Week21,2016 SelfReport-Week22,2016 SelfReport-Week23,2016 InformationForYourReport EngineeringReport-Week#,2016 機器人(Robot) BostonDynamics FarmingRobot Rust相關文章 搜尋引擎(SearchEngine) 資訊安全相關(Security) Clickjacking SecurityissuesinJavaScriptEngine 資源 逆向工程(ReverseEngineering) SGX(SecureGuardExtensions) Security SecurityLibs SIMD 運用SIMD來加速的演算法 SIMD 同步(Synchronization) 測試(Testing) ChaosEngineering Fuzzer TestMobileApp MutationTest 檢查伺服器設定 版本控制(VersionControl) Mercurial Pijul 虛擬化(Virtualization) Bareflank bhyve KVM QEMU 視覺化(Visualization) Wiki wdv4758h-notes Docs» Heap（堆） EditonGitHub Heap（堆）¶ 目錄 Heap（堆） Heap基本介紹 常見操作 BinaryHeap BinomialHeap FibonacciHeap 實作 實作概況 BinaryHeap Rust Python 參考 Heap基本介紹¶ 這裡的Heap指的是資料結構上的Heap， 不是在討論記憶體時所提到的Heap（動態分配的記憶體）。

Heap是特殊的樹狀資料結構， 它符合Heap的性質， 也就是每對父節點和其子節點都符合同樣的關聯（例如：大於、小於）。

當所有父節點都大於其子節點時，就稱其為「MaxHeap」。

當所有父節點都小於其子節點時，就稱其為「MinHeap」。

Heap不是完全排序過的資料結構，但可以視為部份有序。

Heap常被作為PriorityQueue（一種AbstractDataType）的實作方式。

而一個Heap常見的實作為BinaryHeap，它的樹為CompleteBinaryTree。

Heap在一些圖論的演算法中扮演極其重要的地位，例如Dijkstra演算法。

其他還有在排序中的使用，例如Heapsort。

常見操作¶ 基本： find-min/find-max insert extract-min/extract-max delete-min/delete-max replace 建立： create-heap heapify merge(union) meld 檢視： size is-empty 內部： decrease-key/increase-key delete shift-up shift-down BinaryHeap¶ find-min Θ(1) delete-min Θ(logn) insert Θ(logn) decrease-key Θ(logn) merge Θ(n) BinomialHeap¶ BinomialHeap是和BinaryHeap相似的結構， 但是支援快速合併兩個Heap（時間複雜度為O(logn)）。

一個orderk的BinomialHeap會擁有2^k個節點和高度k。

而BinomialHeap的名稱就來自於 「在ordern時，在深度d會擁有C(n;k)個節點。

」（Binomialcoefficient）。

0 1 0（只有root） 1 (order0)add2^0=2 1 2 (order1)add2^1=4 2 3 (order2)add2^2=8 3 由途中可以看出這結構特殊的結構在合併兩個orderk-1的Heap時， 只需要把其中一個Heap作為子樹接在最左邊就可以形成新的orderk的Heap了。

find-min Θ(1) delete-min Θ(logn) insert O(logn)（同merge一個點）,Θ(1)（Amortized） decrease-key Θ(logn) merge O(logn)（n是比較大的Heap的size） FibonacciHeap¶ FibonacciHeap是由MichaelL.Fredman和RobertE.Tarjan 在1984年發明的資料結構， 並在1987年發佈在一個科學期刊上。

FibonacciHeap的名稱源自該資料結構內部使用的Fibonacci數字。

FibonacciHeap跟其他Heap資料結構（例如BinaryHeap、BinomialHeap）比起來， 有較好的Amortized執行時間。

理論的執行時間和在實務上的狀況並不完全一樣， 實務上BinaryHeap常因為Array-based的實作 而比FibonacciHeap有更好的效能， 所以FibonacciHeap其實沒有很常被使用。

實作¶ 實作概況¶ Heap通常會使用Array（固定大小或動態決定大小）， 如此一來每個資料間就不需要指標來連繫。

當有新的資料插入Heap或從Heap中移除時， Heap的性質可能會被違反， 此時就必須利用內部的操作平衡。

想從已經有資料的Array建立Heap可利用Floyd演算法， 該演算法只需要線性（Linear）時間即可建立（O(n)）， 比起從空的Heap開始建立所需的對數線性（Log-linear）時間（O(nlogn)）還要快。

BinaryHeap¶ Rust¶ std::collections::BinaryHeap https://doc.rust-lang.org/std/collections/binary_heap/ popinglargest O(logn) checkinglargest O(1) vectortobinaryheap(in-place) O(n) binaryheaptosortedvector(in-place) O(nlogn) Python¶ heapq https://docs.python.org/3/library/heapq.html 參考¶ Wikipedia-Heap(datastructure) Wikipedia-Fibonacciheap Wikipedia-Binomialheap ReadtheDocs v:latest Versions latest Downloads htmlzip OnReadtheDocs ProjectHome Builds FreedocumenthostingprovidedbyReadtheDocs.