Heap

堆積結構

背景知識

最大最小堆積
python

理解問題

建構堆積取得最大最小值。

Java

Heap is use for PriorityQueue

TC:
Offer(), add(): O(logn) // because heap is tree structure
Poll(), remove(): O(logn)
peek(): O(1)
contains: O(n)
Nlargest/Nsmallest: O(n)

SC:
O(n)

import java.util.*;

class Main {
    private static void findNHighest(List<Integer> list, int n) {
        Queue<Integer> nthHighest = new PriorityQueue<>();
    
        for (Integer each : list) {
            nthHighest.add(each);
            if (nthHighest.size() > n) {
                nthHighest.poll();
            }
        }
        System.out.println(nthHighest);
    }
    
    public static void  findNSmallest(List<Integer>  list, int  n){
        // reverseOrder
        Queue<Integer> nthHighest = new PriorityQueue<>(Collections.reverseOrder());
        
        for (Integer each : list) {
            nthHighest.add(each);
            if (nthHighest.size() > n) {
                nthHighest.poll();
            }
        }
        System.out.println(nthHighest);
    }
    
    public static void main(String[] args) {
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        numbers.add(5);
        numbers.add(7);
        numbers.add(9);
        numbers.add(1);
        numbers.add(3);
        
        System.out.println("PriorityQueue: " + numbers+ "\n");
        numbers.add(4);
        System.out.println("Added PriorityQueue: " + numbers+ "\n");
        
        // deep copy
        PriorityQueue<Integer> dcpNumbers = new PriorityQueue<>();
        Iterator<Integer> iterate = numbers.iterator();
        while(iterate.hasNext()) {
                dcpNumbers.add(iterate.next());
        }
        
        System.out.println("Head(smallest): " + numbers.peek()); 
        System.out.println("Pop the smallest: " + numbers.poll()); 
        System.out.println("PriorityQueue: " + numbers+ "\n");
        System.out.println("Org PriorityQueue: " + dcpNumbers+ "\n");
        
        List nlist = new ArrayList(numbers);// queue to list
        findNHighest(nlist, 3);

        List dcplist = new ArrayList(dcpNumbers);// queue to list
        findNSmallest(dcplist, 3);
    }
}

>
java -cp /tmp/jmyNEzLB54 Main
PriorityQueue: [1, 3, 9, 7, 5]
Added PriorityQueue: [1, 3, 4, 7, 5, 9]
Head(smallest): 1
Pop the smallest: 1
PriorityQueue: [3, 5, 4, 7, 9]

Org PriorityQueue: [1, 3, 4, 7, 5, 9]

[5, 9, 7]
[4, 1, 3]

Implement

Python

TC: Push/Pop: O(logn), Nlargest/Nsmallest: [Python]O(nlogn)
SC: O(n)

import heapq, copy

li = [5, 7, 9, 1, 3]
heapq.heapify(li) # to heap
print(li)

heapq.heappush(li, 4)
print(li)

cp = copy.deepcopy(li) # deep copy original list
print(cp)
print(heapq.heappop(li)) # pop the smallest

print(heapq.nlargest(3, cp)) # 3 largest
print(heapq.nsmallest(3, cp)) # 3 smallest

print(cp)

>
[1, 3, 9, 7, 5]
[1, 3, 4, 7, 5, 9]
[1, 3, 4, 7, 5, 9]
1
[9, 7, 5]
[1, 3, 4]
[1, 3, 4, 7, 5, 9]

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)