国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

我理解的數(shù)據(jù)結(jié)構(gòu)(七)—— 堆和優(yōu)先隊列(Heap And PriorityQueue)

I_Am / 2113人閱讀

摘要:我理解的數(shù)據(jù)結(jié)構(gòu)七堆和優(yōu)先隊列一堆堆的基礎(chǔ)堆也是一顆樹堆最為主流的一種實現(xiàn)方式二叉堆二叉堆是一顆完全二叉樹完全二叉樹完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹是由滿二叉樹而引出來的。

我理解的數(shù)據(jù)結(jié)構(gòu)(七)—— 堆和優(yōu)先隊列(Heap And PriorityQueue) 一、堆

1.堆的基礎(chǔ)

堆也是一顆樹

堆最為主流的一種實現(xiàn)方式:二叉堆

二叉堆是一顆完全二叉樹

2.完全二叉樹

完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹是由滿二叉樹而引出來的。對于深度為K的,有n個結(jié)點的二叉樹,當且僅當其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。
(通俗來說:完全二叉樹不一定是滿二叉樹,當一層已滿容納不下新的節(jié)點時,新的一層從左至右來盛放新節(jié)點,缺失的節(jié)點一定在右側(cè))

最大堆:堆中某個節(jié)點的值總是不大于其父節(jié)點的值(相應(yīng)的,可以定義最小堆)

3.用數(shù)組存儲二叉堆

4.基礎(chǔ)代碼實現(xiàn)

這里的ArrayNew是我之前實現(xiàn)的數(shù)組:數(shù)組代碼
public class Heap> {

    private ArrayNew data;

    public Heap(int capacity) {
        data = new ArrayNew<>(capacity);
    }

    public Heap() {
        data = new ArrayNew<>();
    }

    // 返回堆中的元素個數(shù)
    public int size() {
        return data.getSize();
    }

    // 堆中是否包含元素
    public boolean isEmpty() {
        return data.isEmpty();
    }

    // 父節(jié)點的索引
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn"t have parent");
        }
        return (index - 1) / 2;
    }

    // 左子節(jié)點的索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    // 右子節(jié)點的索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }

}

5.添加元素(sift up

步驟:

在最后一層的最后添加這個元素,如果是滿樹,則在新的一層最左端添加

與其父節(jié)點做比較,如果父節(jié)點小于當前元素的節(jié)點,置換位置

以此類推,直到比較至根節(jié)點

// 添加元素
public void add(E e) {
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

// 上浮
private void siftUp(int index) {

    // 添加的元素大于父節(jié)點的元素
    while (index > 0 && data.get(index).compareTo(data.get(parent(index))) > 0) {
        data.swap(index, parent(index));
        index = parent(index);
    }
}

6.取出元素(sift down

步驟:

最后一個節(jié)點與根節(jié)點交換,取出末尾節(jié)點,這樣整體樹結(jié)構(gòu)不會改變,只是位置不對

根節(jié)點與子節(jié)點的元素做比較,如果比子節(jié)點的最大的節(jié)點元素小,則置換位置

以此類推,直至比子節(jié)點的元素都大

// 查看堆中的最大值
public E findMax() {
    if (data.isEmpty()) {
        throw new IllegalArgumentException("can"t find Max in empty heap");
    }

    return data.get(0);
}

// 取出堆中的最大值
public E extractMax() {
    E ret = data.get(0);

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);
    return ret;
}

// 下沉
private void siftDown(int index) {

    while (leftChild(index) < data.getSize()) { // 有子節(jié)點(左子節(jié)點沒有越界)

        int j = leftChild(index);

        // 有右子節(jié)點,并且右節(jié)點元素大于左節(jié)點元素
        if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
            j = j + 1;
        }

        // 此時,data[j]就是左右子節(jié)點的最大節(jié)點值

        if (data.get(j).compareTo(data.get(index)) <= 0) {
            break;
        }

        data.swap(index, j);
        index = j;
    }
}

7.Heapify和replace

replace(取出堆中的最大元素,再放入一個新的元素)

實現(xiàn):可以先extractMaxadd,但是這樣會有兩次O(logn)操作

優(yōu)化:可以將堆頂元素替換以后再siftDown,這樣只有一次O(logn)操作

// 取出堆中的最大元素,并替換成元素e,重新siftDown
public E replace(E e) {
    E ret = data.get(0);
    data.set(0, e);
    siftDown(0);
    return ret;
}

heapify(將任意數(shù)組整理成堆的形狀)

實現(xiàn):將n個元素逐個插入到一個空堆中,算法復雜度是O(logn)

優(yōu)化:heapify(算法復雜度是O(n))

將任意一個數(shù)組看成完全二叉樹(盡管元素的位置不對)

找到最后一個非葉子節(jié)點(最后一個節(jié)點的父節(jié)點)

從最后一個非葉子節(jié)點倒著不斷的對每個節(jié)點siftDown就可以了

// heapify
public Heap(E[] arr) {
    data = new ArrayNew<>(arr);
    for (int i = parent(data.getSize() - 1); i > 0; i--) {
        siftDown(i);
    }
}

8. 復雜度分析

因為堆的取出和添加復雜度都是O(logn),所以堆的性能是很高的。
操作 時間復雜度
add O(logn)
extractMax O(logn)
二、優(yōu)先隊列

1.優(yōu)先隊列基礎(chǔ)

普通隊列:先進先出,后進后出

優(yōu)先隊列:出隊順序和入隊順序無關(guān),和優(yōu)先級有關(guān)

2.隊列接口

public interface Queue {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    // 查看隊首元素
    E getFront();
}

3.基于堆的優(yōu)先隊列代碼實現(xiàn)

public class priorityQueue> implements Queue {

    Heap data;

    public priorityQueue() {
        data = new Heap<>();
    }

    @Override
    public int getSize() {
        return data.size();
    }

    @Override
    public boolean isEmpty() {
        return data.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        data.add(e);
    }

    @Override
    public E dequeue() {
        return data.extractMax();
    }

    @Override
    public E getFront() {
        return data.findMax();
    }
}

4.LeetCode中有關(guān)優(yōu)先隊列的問題

347. 前K個高頻元素

題目:347. 前K個高頻元素

描述:給定一個非空的整數(shù)數(shù)組,返回其中出現(xiàn)頻率前 k 高的元素。

例子:

示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:
輸入: nums = [1], k = 1
輸出: [1]

解決代碼:

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

// 只需要在`Solution`這個類中引入所需要的類即可
// 所有的類都可以在之前的博客中找到
public class Solution {

    private class Freq implements Comparable {
        public int e, freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another) {
            if (this.freq < another.freq) {
                return 1;
            } else if (this.freq > another.freq) {
                return -1;
            } else {
                return 0;
            }
        }
    }

    public List topKFrequent(int[] nums, int k) {

        TreeMap map = new TreeMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        PriorityQueue pq = new PriorityQueue<>();
        for (int key : map.keySet()) {
            if (pq.getSize() < k) {
                pq.enqueue(new Freq(key, map.get(key)));
            } else if (map.get(key) > pq.getFront().freq) {
                pq.dequeue();
                pq.enqueue(new Freq(key, map.get(key)));
            }
        }

        ArrayList list = new ArrayList<>();
        while (!pq.isEmpty()) {
            list.add(pq.dequeue().e);
        }
        return list;
    }

}

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/29555.html

相關(guān)文章

  • 理解數(shù)據(jù)結(jié)構(gòu))—— 堆和優(yōu)先隊列Heap And PriorityQueue

    摘要:我理解的數(shù)據(jù)結(jié)構(gòu)七堆和優(yōu)先隊列一堆堆的基礎(chǔ)堆也是一顆樹堆最為主流的一種實現(xiàn)方式二叉堆二叉堆是一顆完全二叉樹完全二叉樹完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹是由滿二叉樹而引出來的。 我理解的數(shù)據(jù)結(jié)構(gòu)(七)—— 堆和優(yōu)先隊列(Heap And PriorityQueue) 一、堆 1.堆的基礎(chǔ) 堆也是一顆樹 堆最為主流的一種實現(xiàn)方式:二叉堆 二叉堆是一顆完全二叉樹 2.完全二叉樹 ...

    Simon 評論0 收藏0
  • PHP面試:說下什么是堆和堆排序?

    摘要:一個常見的例子就是優(yōu)先隊列,還有排序算法之一的堆排序。另外我們還將學習堆排序,并將使用實現(xiàn)堆。堆排序在堆排序中,我們需要用給定的值構(gòu)建一個一個堆。偽代碼如下從上面的偽代碼可以看到,堆排序的第一步就是構(gòu)建一個堆。 堆是什么? 堆是基于樹抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu),用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個常見的例子就是優(yōu)先隊列,還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...

    twohappy 評論0 收藏0
  • PyTips 0x10 - Python 堆與優(yōu)先隊列

    摘要:項目地址中內(nèi)置的庫和分別提供了堆和優(yōu)先隊列結(jié)構(gòu),其中優(yōu)先隊列本身也是基于實現(xiàn)的,因此我們這次重點看一下。堆可以用于實現(xiàn)調(diào)度器例見之協(xié)程,更常用的是優(yōu)先隊列例如。 項目地址:https://git.io/pytips Python 中內(nèi)置的 heapq 庫和 queue 分別提供了堆和優(yōu)先隊列結(jié)構(gòu),其中優(yōu)先隊列 queue.PriorityQueue 本身也是基于 heapq 實現(xiàn)的,因...

    dreambei 評論0 收藏0
  • [Leetcode] Merge Two Sorted Lists Merge K Sorted L

    摘要:注意因為堆中是鏈表節(jié)點,我們在初始化堆時還要新建一個的類。代碼初始化大小為的堆拿出堆頂元素將堆頂元素的下一個加入堆中 Merge Two Sorted Lists 最新更新請見:https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...

    stefanieliang 評論0 收藏0
  • 堆和索引堆python實現(xiàn)

    摘要:堆分為大根堆和小根堆,大根堆是父節(jié)點大于左右子節(jié)點,并且左右子樹也滿足該性質(zhì)的完全二叉樹。其中表示向下取整。則一直指向,一直指向,因為我們在調(diào)整堆結(jié)構(gòu)中實際調(diào)整的是索引數(shù)組,而不會改變真實存放數(shù)據(jù)的數(shù)組。以上就是實現(xiàn)對和索引堆的具體方式。 堆是一棵完全二叉樹。堆分為大根堆和小根堆,大根堆是父節(jié)點大于左右子節(jié)點,并且左右子樹也滿足該性質(zhì)的完全二叉樹。小根堆相反??梢岳枚褋韺崿F(xiàn)優(yōu)先隊列。...

    寵來也 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<