Massive Algorithms: Heap

Showing posts with label Heap. Show all posts

Puzzles, Maths and Algorithms: Finding Relevant Keywords from Large Corpus of Text

Puzzles, Maths and Algorithms: Finding Relevant Keywords from Large Corpus of Text
Problem 1: Given a large paragraph of words containing n words (separated by space), and k keywords. Find the smallest distance between these keywords in the paragraph.

To illustrate the problem, consider that the paragraph is A B A C E D O A B. Let us say that we are interested in two keywords A and D. Then the closest they appear is at position 8 and 6 (D O A) and the minimum distance is 1 (i.e. number of non-keyword words between them).

Build an efficient algorithm with O(k) space and O(n log k) running cost.
To solve this problem, we need to register the last seen position of each of k keywords, as we read the paragraph word-by-word. If the next word, and if that matches a keyword, we need to update the last seen position of the matching keyword and also compute the minimum of the position register. That helps us find the smallest distance.

In order to implement this efficiently, we need a hash map and min heap (tree based implementation, not array based). Following is the code to solve this problem.

Let K[i] indicate ith keyword.
Let W[i] indicate ith word in the paragraph. 

// init map and heap
map = {}
heap = []
for i in 1 to k

  // init heap with -Inf as position of the keyword
  node = heap_node()
  node.val = -Inf

  // map stores the keyword and its pointer to node in the heap
  heap.put(node)
  map.put(K[i], node)
end

idx_start = 0
idx_end = 0
min_dist = Inf
for i in 1 to n
  w = W[i]

  // check if w is one of the keywords, if not ignore
  if !map.contains_key(w)
    continue
  end

  // get the heap node corresponding to the
  // key W[i] and update its position
  node = map.get(w)
  node.val = i

  // re-heapify the min heap
  heap.heapify()

  // min of all positions
  idx = heap.min()

  // if idx = -Inf then some keywords are not seen yet.
  if idx == -Inf
    continue
  end

  // compute distance between keywords
  dist = i - idx - k + 1
  if dist < min_dist
    idx_start = idx
    idx_end = i
    min_dist = dist
  end 
end

The above algorithm requires O(k) memory for the map and the heap. For each word, it requires O(log k) to re-heapify the min heap.

Problem 2: Given a large paragraph of words (separated by space). Consider N tuples of names and interests. If a given person and their interest appears within K words then its a match else not. Find all matches from the paragraph.

To illustrate the problem, consider that the paragraph is "John likes swimming and Jack likes Tennis". Let the interest map is <john swimming>, <john tennis>, <jack swimming>, <jack tennis>. For k = 3, 4, 5, 6 the matches found in the paragraph are <john swimming>, <jack swimming>, <jack tennis>.

Propose an efficient algorithm for two cases: k is small, k is very large.
Read full article from Puzzles, Maths and Algorithms: Finding Relevant Keywords from Large Corpus of Text

Implementing Heapsort in Java and C · Edd Mann

Implementing Heapsort in Java and C · Edd Mann
the first step is to create a heap structure from the input. Calling the ‘heapify’ method on the first half of the input array guarantees (by recursion) to build up the heap data structure and fulfill the heap property. Once this step has completed we loop through each item in the heap, swapping the first and last heap elements, reducing and reconstructing the structure after each iteration.

public class Heap {

    private static int total;

    private static void swap(Comparable[] arr, int a, int b)
    {
        Comparable tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    private static void heapify(Comparable[] arr, int i)
    {
        int lft = i * 2;
        int rgt = lft + 1;
        int grt = i;

        if (lft <= total && arr[lft].compareTo(arr[grt]) > 0) grt = lft;
        if (rgt <= total && arr[rgt].compareTo(arr[grt]) > 0) grt = rgt;
        if (grt != i) {
            swap(arr, i, grt);
            heapify(arr, grt);
        }
    }

    public static void sort(Comparable[] arr)
    {
        total = arr.length - 1;

        for (int i = total / 2; i >= 0; i--)
            heapify(arr, i);

        for (int i = total; i > 0; i--) {
            swap(arr, 0, i);
            total--;
            heapify(arr, 0);
        }
    }
}

http://www.sanfoundry.com/java-program-implement-heap-sort/

```
public class HeapSort 
```
```
{    
```
```
    private static int N;
```
```
    /* Sort Function */
```
```
    public static void sort(int arr[])
```
```
    {       
```
```
        heapify(arr);        
```
```
        for (int i = N; i > 0; i--)
```
```
        {
```
```
            swap(arr,0, i);
```
```
            N = N-1;
```
```
            maxheap(arr, 0);
```
```
        }
```
```
    }     
```
```
    /* Function to build a heap */   
```

    public static void heapify(int arr[])

```
    {
```
```
        N = arr.length-1;
```
```
        for (int i = N/2; i >= 0; i--)
```
```
            maxheap(arr, i);        
```
```
    }
```

    /* Function to swap largest element in heap */

    public static void maxheap(int arr[], int i)

```
    { 
```
```
        int left = 2*i ;
```
```
        int right = 2*i + 1;
```
```
        int max = i;
```

        if (left <= N && arr[left] > arr[i])

```
            max = left;
```

        if (right <= N && arr[right] > arr[max])

```
            max = right;
```
```
 
```
```
        if (max != i)
```
```
        {
```
```
            swap(arr, i, max);
```
```
            maxheap(arr, max);
```
```
        }
```
```
    }    
```

    /* Function to swap two numbers in an array */

    public static void swap(int arr[], int i, int j)

```
    {
```
```
        int tmp = arr[i];
```
```
        arr[i] = arr[j];
```
```
        arr[j] = tmp; 
```
```
    }      
```
```
}
```

http://www.code2learn.com/2011/09/heapsort-array-based-implementation-in.html

http://massivealgorithms.blogspot.com/2015/08/heapsort-vs-quicksort.html
3.1 为什么堆排比快排慢

回顾一下堆排的过程：

1. 建立最大堆（堆顶的元素大于其两个儿子，两个儿子又分别大于它们各自下属的两个儿子… 以此类推）

2. 将堆顶的元素和最后一个元素对调（相当于将堆顶元素（最大值）拿走，然后将堆底的那个元素补上它的空缺），然后让那最后一个元素从顶上往下滑到恰当的位置（重新使堆最大化）。

3. 重复第2步。

这里的关键问题就在于第2步，堆底的元素肯定很小，将它拿到堆顶和原本属于最大元素的两个子节点比较，它比它们大的可能性是微乎其微的。实际上它肯定小于其中的一个儿子。而大于另一个儿子的可能性非常小。于是，这一次比较的结果就是概率不均等的，根据前面的分析，概率不均等的比较是不明智的，因为它并不能保证在糟糕情况下也能将问题的可能性削减到原本的1/2。可以想像一种极端情况，如果a肯定小于b，那么比较a和b就会什么信息也得不到——原本剩下多少可能性还是剩下多少可能性。

在堆排里面有大量这种近乎无效的比较，因为被拿到堆顶的那个元素几乎肯定是很小的，而靠近堆顶的元素又几乎肯定是很大的，将一个很小的数和一个很大的数比较，结果几乎肯定是“小于”的，这就意味着问题的可能性只被排除掉了很小一部分。

这就是为什么堆排比较慢（堆排虽然和快排一样复杂度都是O(NlogN)但堆排复杂度的常系数更大）。

MacKay也提供了一个修改版的堆排：每次不是将堆底的元素拿到上面去，而是直接比较堆顶（最大）元素的两个儿子，即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的，两者都很大，说不好哪个更大哪个更小，所以这次比较的两个结果就是概率均等的了。具体参考这里。

http://users.aims.ac.za/~mackay/sorting/sorting.html

Read full article from Implementing Heapsort in Java and C · Edd Mann

Connect n ropes with minimum cost - GeeksforGeeks

Connect n ropes with minimum cost - GeeksforGeeks
There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

the lengths of the ropes which are picked first are included more than once in total cost. Therefore, the idea is to connect smallest two ropes first and recur for remaining ropes. This approach is similar to Huffman Coding. We put smallest ropes down the tree so that they can be repeated multiple times rather than the longer ropes.

int minCost(int arr[], int n)

{

    // Create a priority queue ( http://www.cplusplus.com/reference/queue/priority_queue/ )

    // By default 'less' is used which is for decreasing order

    // and 'greater' is used for increasing order

    priority_queue< int, vector<int>, greater<int> > pq(arr, arr+n);

    // Initialize result

    int res = 0;

    // While size of priority queue is more than 1

    while (pq.size() > 1)

{

        // Extract shortest two ropes from pq

        int first = pq.top();

        pq.pop();

        int second = pq.top();

        pq.pop();

        // Connect the ropes: update result and

        // insert the new rope to pq

        res += first + second;

        pq.push(first + second);

}

    return res;

}

Read full article from Connect n ropes with minimum cost - GeeksforGeeks

Puzzles, Maths and Algorithms: Finding Relevant Keywords from Large Corpus of Text

Implementing Heapsort in Java and C · Edd Mann

Connect n ropes with minimum cost - GeeksforGeeks

Labels

Popular Posts