- Forum
- General C++ Programming
- heaps
heaps
and column (x) having an intensity F(x,y). For an image of size N x N pixels, the values of x and y range between 0 and N-1. The gray-level intensity F(x,y) is usually an integer between 0 and 255, with 0 representing pure black and 255 representing pure white.
Given such image, we would like to find the locations (xi , yi) and (xj , yj) of the pair of pixels (i , j) having the closest intensities F.
The problem can be solved by different methods. The following is an efficient method:
Sort the pixels according to their intensities. After the pixels are sorted, the closest pair will lie next to each other somewhere in sorted order. Thus a linear-time scan through them completes the job. Sorting using HeapSort will cost O(N log N) and the scan will cost O(N) so that the total cost is O(N log N) + O(N) = O(N log N).
1. Implement the PQ (minimum Heap) class.
2. Implement the HeapSort algorithm using the above class.
3. Implement a program to do the following:
• Generate a 2-D array representing an image of size N xN (a typical value of N is 128) with random integer intensities F(x,y) in the range 0 to 255.
• Use HeapSort to sort the intensities.
• Use a linear scan to determine the locations of the pixel pair having the closest intensities.
• Display a sample output.
Given such image, we would like to find the locations (xi , yi) and (xj , yj) of the pair of pixels (i , j) having the closest intensities F.
The problem can be solved by different methods. The following is an efficient method:
Sort the pixels according to their intensities. After the pixels are sorted, the closest pair will lie next to each other somewhere in sorted order. Thus a linear-time scan through them completes the job. Sorting using HeapSort will cost O(N log N) and the scan will cost O(N) so that the total cost is O(N log N) + O(N) = O(N log N).
1. Implement the PQ (minimum Heap) class.
2. Implement the HeapSort algorithm using the above class.
3. Implement a program to do the following:
• Generate a 2-D array representing an image of size N xN (a typical value of N is 128) with random integer intensities F(x,y) in the range 0 to 255.
• Use HeapSort to sort the intensities.
• Use a linear scan to determine the locations of the pixel pair having the closest intensities.
• Display a sample output.
Last edited on
I agree with webJose
(post some code to prove you've at least made an effort and describe the problem you're having, then you'll get some help)
(post some code to prove you've at least made an effort and describe the problem you're having, then you'll get some help)
Last edited on
Topic archived. No new replies allowed.