【算法】堆

堆

heap，一棵完全二叉樹，使用數組實現的，但具備完全二叉樹的一些性質。一般總是滿足以下性質：

  • 堆中某個節點的值總是不大于或不小于其父節點的值；
  • 堆總是一棵完全二叉樹。（即除了最底層，其他層的節點都被元素填滿，且最底層盡可能地從左到右填入）

堆一般分為以下兩種形式：

  • 大根堆：根節點的值最大，每個節點都大于等于其子樹中所有節點的值
  • 小根堆：根節點的值最小，每個節點都小于等于其子樹中所有節點的值

兩者的總體架構相同，不同的只是元素之間的比較規則

堆的入隊和出隊的時間復雜度都是O(log n)

在PriorityQueue中，最高優先級的元素總是位于隊列的前面，即堆的根節點。（默認是數字越小，優先級越高），常用方法：

  • peek()方法：獲取隊列中優先級最高的元素
  • poll()方法：從隊列中刪除并返回優先級最高的元素
  • add()方法：向隊列中添加元素
  • remove()方法：移除隊列中的某個元素(數組中從左到右的第一個)
  • size()方法：返回當前堆中的元素個數
  • clear()方法：清空堆中的元素，重置堆

PriorityQueue底層使用最小堆來實現，能夠自動維護堆的性質。

在實現堆的過程中，通常使用數組來存儲堆元素，并通過一些算法實現堆的插入、刪除等操作。

小根堆

數組遞歸實現小根堆

import java.util.*;public class MinHeap {private int[] heap;     //用于實現堆的數組private int size;       //當前數組中最后一個元素的索引private int maxSize;    //總數組長度public MinHeap(int maxSize) {this.maxSize = maxSize;this.size = 0;//從索引為1的位置存儲堆中的元素heap = new int[this.maxSize + 1];heap[0] = Integer.MIN_VALUE;}// 獲取傳入元素的父元素private int parent(int pos) {return pos / 2;}// 獲取傳入元素的左子元素private int leftChild(int pos) {return 2 * pos;}// 獲取傳入元素的右子元素private int rightChild(int pos) {return (2 * pos) + 1;}//判斷是否是葉子結點private boolean isLeaf(int pos) {return pos > (size / 2) && pos <= size;}//交換位置private void swap(int pos1, int pos2) {int tmp = heap[pos1];heap[pos1] = heap[pos2];heap[pos2] = tmp;}//小根堆化，對傳入的元素作為父節點的子樹進行重構，用于在插入或刪除元素后重新調整堆以保持小根堆的性質private void minHeapify(int pos) {if (!isLeaf(pos)) {//不是葉子結點//如果父元素比左子元素或右子元素大if (heap[pos] > heap[leftChild(pos)] || heap[pos] > heap[rightChild(pos)]) {//交換父元素和兩子節點中較小的那個元素，然后重構對應的子樹if (heap[leftChild(pos)] < heap[rightChild(pos)]) {swap(pos, leftChild(pos));minHeapify(leftChild(pos));} else {swap(pos, rightChild(pos));minHeapify(rightChild(pos));}}}}//向堆中插入元素public void insert(int element) {if (size >= maxSize) {return;}heap[++size] = element;int current = size;//插入的元素比對應的父元素小，交換位置，不斷向上重構while (heap[current] < heap[parent(current)]) {swap(current, parent(current));current = parent(current);}}//獲取最小的元素，將最后一個元素放入到原最小元素的位置，然后重構public int extractMin() {int popped = heap[1];heap[1] = heap[size--];minHeapify(1);return popped;}//不斷根據父元素打印子節點的元素public void print() {for (int i = 1; i <= size / 2; i++) {System.out.print(" Parent: " + heap[i] + " Left child: " + heap[2 * i] + " Right child: " + heap[2 * i + 1]);System.out.println();}}public static void main(String[] args) {MinHeap minHeap = new MinHeap(10);minHeap.insert(5);minHeap.insert(3);minHeap.insert(17);minHeap.print();System.out.println("The Min val is " + minHeap.extractMin());}
}

數組非遞歸實現小根堆

import java.util.Arrays;public class MinHeap {private int[] heap;private int size;public MinHeap(int capacity) {heap = new int[capacity];size = 0;}public void insert(int val) {if (size == heap.length) {//如果空間不夠則將數組的長度擴充一倍heap = Arrays.copyOf(heap, size * 2);}heap[size++] = val;int i = size - 1;while (i > 0 && heap[i] < heap[(i - 1) / 2]) {int temp = heap[i];heap[i] = heap[(i - 1) / 2];heap[(i - 1) / 2] = temp;i = (i - 1) / 2;}}public int pop() {if (size == 0) {throw new IllegalStateException("Heap is empty");}int root = heap[0];heap[0] = heap[--size];int i = 0;while (i * 2 + 1 < size) {int child = i * 2 + 1;//如果右節點存在而且比左節點小，則指向右節點，否則指向左節點if (child + 1 < size && heap[child + 1] < heap[child]) {child++;}if (heap[child] < heap[i]) {int temp = heap[i];heap[i] = heap[child];heap[child] = temp;i = child;} else {break;}}return root;}public boolean isEmpty() {return size == 0;}
}

在 insert() 方法中，先將元素插入數組末尾，然后將其上移至合適位置，直到父節點小于等于該元素或者該元素上移到根節點為止。在 pop() 方法中，將根節點彈出后，將數組末尾元素放置根節點處，然后將其下移至合適位置，直到子節點大于等于該元素或者該元素下移到葉子節點為止。

非遞歸實現，因此空間復雜度較遞歸實現會小一些，但是代碼實現會更加復雜。

非遞歸實現中需要學習的還有：

拋出異常

if (size == 0) {throw new IllegalStateException("Heap is empty");
}

擴充堆大小

heap = Arrays.copyOf(heap, size * 2);

PriorityQueue實現小根堆

	public static void main(String[] args) {//可以直接使用PriorityQueue實現小根堆，因為PriorityQueue內部默認就是使用小根堆實現的//PriorityQueue<Integer> minHeap = new PriorityQueue<>();//傳入了一個Comparator對象，重寫了compare方法，使得PriorityQueue中的元素按照從小到大的順序排列。PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {public int compare(Integer a, Integer b) {return a - b;}});minHeap.add(10);minHeap.add(20);minHeap.add(15);System.out.println("Smallest element: " + minHeap.peek());System.out.println("Removed element: " + minHeap.poll());System.out.println("New smallest element: " + minHeap.peek());}

小根堆的實現可以使用Java中的PriorityQueue類，只需要在創建PriorityQueue對象時傳入一個Comparator對象，實現Comparator的compare方法來定義小根堆的比較方式。

大根堆

數組遞歸實現大根堆

import java.util.*;public class MaxHeap {private int[] heap;     //用于實現堆的數組private int size;       //當前數組中最后一個元素的索引private int maxSize;    //總數組長度public MaxHeap(int maxSize) {this.maxSize = maxSize;this.size = 0;//從索引為1的位置存儲堆中的元素heap = new int[this.maxSize + 1];heap[0] = Integer.MAX_VALUE;}// 獲取傳入元素的父元素private int parent(int pos) {return pos / 2;}// 獲取傳入元素的左子元素private int leftChild(int pos) {return 2 * pos;}// 獲取傳入元素的右子元素private int rightChild(int pos) {return (2 * pos) + 1;}//判斷是否是葉子結點private boolean isLeaf(int pos) {return pos > (size / 2) && pos <= size;}//交換位置private void swap(int pos1, int pos2) {int tmp = heap[pos1];heap[pos1] = heap[pos2];heap[pos2] = tmp;}//小根堆化，對傳入的元素作為父節點的子樹進行重構private void maxHeapify(int pos) {if (!isLeaf(pos)) {//不是葉子結點//如果父元素比左子元素或右子元素小if (heap[pos] < heap[leftChild(pos)] || heap[pos] < heap[rightChild(pos)]) {//交換父元素和兩子節點中較小的那個元素，然后重構對應的子樹if (heap[leftChild(pos)] > heap[rightChild(pos)]) {swap(pos, leftChild(pos));maxHeapify(leftChild(pos));} else {swap(pos, rightChild(pos));maxHeapify(rightChild(pos));}}}}//向堆中插入元素public void insert(int element) {if (size >= maxSize) {return;}heap[++size] = element;int current = size;//插入的元素比對應的父元素小，交換位置，不斷向上重構while (heap[current] > heap[parent(current)]) {swap(current, parent(current));current = parent(current);}}//獲取最小的元素，將最后一個元素放入到原最小元素的位置，然后重構public int extractMax() {int popped = heap[1];heap[1] = heap[size--];maxHeapify(1);return popped;}//不斷根據父元素打印子節點的元素public void print() {for (int i = 1; i <= size / 2; i++) {System.out.print(" Parent: " + heap[i] + " Left child: " + heap[2 * i] + " Right child: " + heap[2 * i + 1]);System.out.println();}}public static void main(String[] args) {MaxHeap maxHeap = new MaxHeap(10);maxHeap.insert(5);maxHeap.insert(3);maxHeap.insert(17);maxHeap.print();System.out.println("The Max val is " + maxHeap.extractMax());}
}

PriorityQueue實現大根堆

	public static void main(String[] args) {// 傳入了一個Comparator對象，重寫了compare方法，使得PriorityQueue中的元素按照從大到小的順序排列。PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {public int compare(Integer a, Integer b) {return b - a;}});maxHeap.add(10);maxHeap.add(20);maxHeap.add(15);System.out.println("Max element: " + maxHeap.peek());System.out.println("Removed element: " + maxHeap.poll());System.out.println("New Max element: " + maxHeap.peek());}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/70563.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/70563.shtml
英文地址，請注明出處：http://en.pswp.cn/web/70563.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

C/C++高性能Web開發框架全解析：2025技術選型指南

C/C++高性能Web開發框架全解析：2025技術選型指南

一、工業級框架深度解析&#xff08;附性能實測&#xff09; 1. Drogon v2.1&#xff1a;異步框架性能王者 核心架構&#xff1a; Reactor 非阻塞I/O線程池&#xff08;參考Nginx模型&#xff09; 協程實現&#xff1a;基于Boost.Coroutine2&#xff08;兼容C11&#xff09;…
閱讀更多...
使用PHP接入純真IP庫：實現IP地址地理位置查詢

使用PHP接入純真IP庫：實現IP地址地理位置查詢

引言 在日常開發中，我們經常需要根據用戶的IP地址獲取其地理位置信息，例如國家、省份、城市等。純真IP庫（QQWry）是一個常用的IP地址數據庫，提供了豐富的IP地址與地理位置的映射關系。本文將介紹如何使用PHP接入純真IP庫，并通過一個完整的案例演示如何實現IP地址的地理位…
閱讀更多...
Django ORM 的常用字段類型、外鍵關聯的跨表引用技巧，以及 `_` 和 `__` 的使用場景

Django ORM 的常用字段類型、外鍵關聯的跨表引用技巧，以及 `_` 和 `__` 的使用場景

一、Django ORM 常用字段類型 1. 基礎字段類型 字段類型說明示例CharField字符串字段&#xff0c;必須指定 max_lengthname models.CharField(max_length50)IntegerField整數字段age models.IntegerField()BooleanField布爾值字段is_active models.BooleanField()DateFiel…
閱讀更多...
java遞歸求自然數列的前n項和

java遞歸求自然數列的前n項和

概述 實現 /*** 數列 1 2 3 ... n ...* 遞歸求數列的前n項和* param n* return*/private static long calSum(long n){if (n1) return 1;else {return ncalSum(n-1); // 前n項的和 即第n項的值前n-1項的和}}測試用例 public static void main(String[] args) {long res1 cal…
閱讀更多...
【Golang 面試題】每日 3 題（六十五）

【Golang 面試題】每日 3 題（六十五）

?個人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;專欄地址&#xff1a;http://t.csdnimg.cn/UWz06 &#x1f4da;專欄簡介&#xff1a;在這個專欄中&#xff0c;我將會分享 Golang 面試中常見的面試題給大家~ ??如果有收獲的話&#xff0c;歡迎點贊&#x1f44d;收藏…
閱讀更多...
16、Python面試題解析：python中的淺拷貝和深拷貝

16、Python面試題解析：python中的淺拷貝和深拷貝

在 Python 中&#xff0c;淺拷貝&#xff08;Shallow Copy&#xff09; 和 深拷貝&#xff08;Deep Copy&#xff09; 是處理對象復制的兩種重要機制&#xff0c;它們的區別主要體現在對嵌套對象的處理方式上。以下是詳細解析&#xff1a; 1. 淺拷貝&#xff08;Shallow Copy&a…
閱讀更多...
【Godot4.3】題目與答案解析合并器

【Godot4.3】題目與答案解析合并器

免責申明 本文和工具截圖中涉及題庫和題目&#xff0c;均為本人自學使用&#xff0c;并未有商業和傳播企圖。如有侵害&#xff0c;聯系刪改。 概述 筆者本人醫學專業從業人員&#xff0c;編程只是業余愛好。在自己的專業應考學習過程當中&#xff1a; 有時候不太喜歡紙質題庫…
閱讀更多...
Lm studio本地部署DeepSeek

Lm studio本地部署DeepSeek

為什么用Lm studio Ollama官網下載過慢或失敗&#xff08;Lm默認下載源無法下載&#xff0c;但可以更換下載源&#xff09;Ollama默認安裝至C盤一部分Nivida顯卡無法吃滿顯存資源一部分AMD顯卡替換rocm文件后無法啟動 Lm studio安裝 官網下載&#xff1a;LM Studio - Discov…
閱讀更多...
基于Qlearning強化學習的2DoF機械臂運動控制系統matlab仿真

基于Qlearning強化學習的2DoF機械臂運動控制系統matlab仿真

目錄 1.算法仿真效果 2.算法涉及理論知識概要 2.1 2DoF機械臂運動學模型 2.2 Q-learning強化學習算法原理 3.MATLAB核心程序 4.完整算法代碼文件獲得 1.算法仿真效果 matlab2022a仿真結果如下&#xff08;完整代碼運行后無水印&#xff09;&#xff1a; 仿真操作步驟可參…
閱讀更多...
Unity貼圖與模型相關知識

Unity貼圖與模型相關知識

一、貼圖 1.貼圖的類型與形狀 貼圖類型 貼圖形狀 2.在Unity中可使用一張普通貼圖來生成對應的法線貼圖&#xff08;但并不規范&#xff09; 復制一張該貼圖將復制后的貼圖類型改為Normal Map 3.貼圖的sRGB與Alpha sRGB&#xff1a;勾選此選項代表此貼圖存儲于Gamma空間中…
閱讀更多...
快速上手 Unstructured：安裝、Docker部署及PDF文檔解析示例

快速上手 Unstructured：安裝、Docker部署及PDF文檔解析示例

1. 核心概念 1.1 Unstructured簡介 Unstructured 是一個強大的 Python 庫，專注于從非結構化數據中提取和預處理文本信息，廣泛應用于 PDF、Word 文檔、HTML 等多種格式的文件處理。其核心功能包括分區、清理、暫存和分塊，能夠將復雜的非結構化文檔轉換為結構化輸出，為后續…
閱讀更多...
pyecharts介紹

pyecharts介紹

文章目錄 介紹安裝pyecharts基本使用全局配置選項 折線圖相關配置地圖模塊使用柱狀圖使用 介紹 echarts慮是個由百度開源的數據可視化&#xff0c;憑借著良好的交互性&#xff0c;精巧的圖表設計&#xff0c;得到了眾多開發者的認可&#xff0c;而Pyhon是門富有表達力的語言&a…
閱讀更多...
Fisher信息矩陣與Hessian矩陣：區別與聯系全解析

Fisher信息矩陣與Hessian矩陣：區別與聯系全解析

Fisher信息矩陣與Hessian矩陣&#xff1a;區別與聯系全解析 在統計學和機器學習中&#xff0c;Fisher信息矩陣&#xff08;FIM&#xff09;和Hessian矩陣是兩個經常出現的概念&#xff0c;它們都與“二階信息”有關&#xff0c;常用來描述函數的曲率或參數的敏感性。你可能聽說…
閱讀更多...
python與C系列語言的差異總結（1）

python與C系列語言的差異總結（1）

/ 表示浮點除法 // 表示整數除法 print(8/3)print(8//3)布爾型 False/True 首字母大寫 整數的大小是沒有限制的&#xff0c;會根據需要自動增長&#xff0c;僅受限于可用內存的大小。 m**n表示m的n次方 x 4.3 ** 2.4print(x)print(3.5e30 * 2.77e45)print(1000000001.0 *…
閱讀更多...
Python selenium 庫

Python selenium 庫

Selenium 是一個用于自動化 Web 瀏覽器操作的強大工具&#xff0c;廣泛應用于 Web 應用程序測試、網頁數據抓取和任務自動化等場景。 Selenium 為各種編程語言提供了 API&#xff0c;用作測試。 目前的官方 API 文檔有 C#、JavaScript、Java、Python、Ruby。 安裝 Selenium 和…
閱讀更多...
vllm部署LLM（qwen2.5，llama，deepseek）

vllm部署LLM（qwen2.5，llama，deepseek）

目錄 環境 qwen2.5-1.5b-instruct 模型下載 vllm 安裝 驗證安裝 vllm 啟動 查看當前模型列表 OpenAI Completions API&#xff08;文本生成&#xff09; OpenAI Chat Completions API&#xff08;chat 對話&#xff09; vllm 進程查看&#xff0c;kill llama3 deep…
閱讀更多...
Python NumPy庫使用指南：從入門到精通

Python NumPy庫使用指南：從入門到精通

1. 引言 NumPy（Numerical Python）是 Python 中用于科學計算的核心庫之一。它提供了強大的多維數組對象（ndarray），以及一系列高效的數學函數，能夠輕松處理大規模的數值數據。NumPy 是許多其他科學計算庫（如 Pandas、Matplotlib、Scikit-learn 等）的基礎。 本文將詳細介…
閱讀更多...
15.2 智能銷售顧問系統技術架構解密：構建企業級知識驅動型對話引擎

15.2 智能銷售顧問系統技術架構解密：構建企業級知識驅動型對話引擎

智能銷售顧問系統技術架構解密：構建企業級知識驅動型對話引擎 關鍵詞：RAG 架構設計、銷售知識庫系統、LoRA 微調優化、多模態交互引擎、高并發服務部署 1. 系統技術架構全景解析 1.1 核心架構設計圖 #mermaid-svg-UBkTgaR5lf5WfGMa {font-family:"trebuchet ms",…
閱讀更多...
用PyTorch從零構建 DeepSeek R1：模型架構和分步訓練詳解

用PyTorch從零構建 DeepSeek R1：模型架構和分步訓練詳解

DeepSeek R1 的完整訓練流程核心在于&#xff0c;在其基礎模型 DeepSeek V3 之上&#xff0c;運用了多種強化學習策略。 本文將從一個可本地運行的基礎模型起步&#xff0c;并參照其技術報告&#xff0c;完全從零開始構建 DeepSeek R1&#xff0c;理論結合實踐&#xff0c;逐步…
閱讀更多...
爬蟲基礎入門之爬取豆瓣電影Top250-Re正則的使用

爬蟲基礎入門之爬取豆瓣電影Top250-Re正則的使用

網址:豆瓣電影 Top 250 本案例所需要的模塊 requests (用于發送HTTP請求)re (用于字符串匹配和操作) 確定需要爬取的數據 &#xff1a; 電影的名稱電影的年份電影的評分電影評論人數 一. 發送請求 模擬瀏覽器向服務器發送請求 準備工作 -分析頁面: F12 or 右擊點擊檢查 查看…
閱讀更多...
最新文章

Copyright @ 2022~2023